二分查找算法（上下界，边界条件）

本文主要讲解二分查找，阅读完大约需要10分钟
首先二分查找只适用于有序序列，时间复杂度为O(logn)

查找序列中存在某个值

这个比较基本，直接放出代码

int bsearch(int*A, int x, int y, int v){
int mid;
while(x < y) {
mid = x+(y-x)/2;
if(A[mid] == v) return mid;
else if(A[mid] > v) y = mid;
else x = mid+1;
}
return -1;
}

不过需要注意的是判断条件，有时候是x<y，有时候是x<=y，这个问题你可用数学的思维来想想：

1.若传入的y为数组的长度，x为初始位置，此时相当于传入的是左闭右开区间，即 [x，y)，这样当x==y时区间是空区间，可以退出循环。
2.若传入的y值为数组长度-1，就相当于传入的数组区间为[x，y]，这样x==y时还有元素没有判断，所以循环退出条件为x<=y。

查找数组中最初出现时的位置

即数组中存在多个元素等于要查找的值，找出第一个出现的位置，先放出代码：

while(x < y){
mid = x+(y-x)/2;
if(A[mid]>=v) y=mid;
else x=mid+1;
}

首先看见判断条件为x<y，就应该想到传入的区间为左闭右开[x，y),如果数组中不存在v的值会返回一个可以插入v后的下标使数组仍然有序，所以返回的结果区间为[x，y]
当 v<A[mid] 表示右数比v都大，但mid可能，所以结果区间为[x,mid]，即y=mid
当v==A[mid] 所求位置不可能在后面，但有可能是mid，因此区间变为[x,mid]
当v>A[mid] 表示所求结果不可能在左边也不可能是mid，所以区间变为[mid+1,y]

这相当于STL中的lower_bound函数

查找数组中最后出现的下一个位置

while(x < y){
mid = x+(y-x)/2;
if(A[mid]<=v) x=mid+1;
else y=mid;
}

由于需要找出下一个位置，所以当v==A[mid] 时需要将区间缩小为[mid+1,y]，其余的分析与上面相同

这相当于STL中的upper_bound函数

以上是本文全部内容，感谢您的翻阅。