二分查找总结

不考虑重复元素下

循环条件l<=r
mid=(left+right)>>1
(1)如果a[mid]=target return mid
(2)如果a[mid]<target 搜索 [mid+1,right]
(3)如果a[mid]>target 搜索 [left,mid-1]
如果循环推出仍然没有找到，就标志着没有该元素。

二分查找元素起始位置

mid=(left+right)>>1
需要找到一个位置，该位置左边都小于target，右边都大于等于target
循环条件left!=right
(1) a[mid]<target 查找[mid+1,right]
(2) a[mid]>=target 查找[left,mid]
退出循环的时候，判断一下a[left]是否等于target，等于则返回left，否则证明不存在该元素。

int bs1(){
    int l=1;
    int r=n;
    while(l<r){
        int mid=(l+r)>>1;
        if(a[mid]<k)
            l=mid+1;
        else r=mid;
    }
    return a[l]==k?l:-1;
}

二分查找元素结束位置

mid=(left+right+1)>>1
循环条件left<right
(1) a[mid]<=target 查找[mid,right]
(2) a[mid]>target 查找[left,mid-1]
退出循环的时候，判断一下a[left]是否等于target，等于则返回left，否则证明不存在该元素
为什么这种情况下要+1呢，是为了向上取整，事实上，在left+1==right下，如果不向上取整，就会陷入死循环里

int bs2(){
    int l=1;
    int r=n;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(a[mid]>k)
            r=mid-1;
        else l=mid;
    }
    return a[l]==k?l:-1;
}