二分查找的边界值
程序员文章站
2024-03-20 10:24:58
...
lower_bound二分查找（c++）
int begin = 0,end = length;
while(begin < end){
int mid = (end - begin) / 2 + begin; //防止溢出
if(array[mid] < key)
begin = mid + 1;
else
end = mid;
return begin; //此时begin和end指向同一个值
}首先，类似于c++中的迭代器写法，将区间设置为左闭右开区间。
区间的设置对于while判断的取值，begin，end的赋值有着重要的影响。
将end的值设置为length时，while的判断必须写为begin<end,而不能写成begin<=end,因为end的值类似于iterator的end，只能代表终止，没有值，同时由于下面的赋值，可能存在问题，如在[2,2]中查找3。而当中点的值小于key时，对begin赋值为mid+1，是因为array[mid]已经被排除了，所以begin需要从mid+1开始算起，而end=mid也是因为array[mid]被排除而赋值为mid。
二分查找的边界值很麻烦，另外一种左闭右闭区间的方法又对while条件和begin，end的取值有不同的要求。
但是可以在当处理的数据小于5时进行顺序查找，时间类似于二分查找。