如何正确的写出二分查找算法

查找届跟排序届不同，面试常用的算法就这么一种，二分查找。二分查找看似容易，其实写得完全正确还是挺难的，下面总结一下规律。

一个普通的二分查找
int search(vector& v,int target){
    int left=0;
    int right=v.size()-1;
    while(left<=right){
        int mid=(left+right)/2;
        if(v[mid]             left=mid+1;
        else if(v[mid]>target)
            right=mid-1;
        else
            return mid;
    }
    return -1;
}

另外一种也很普通的二分查找
int search(vector& v,int target){
    int left=0;
    int right=v.size();
    while(left         int mid=(left+right)/2;
        if(v[mid]             left=mid+1;
        else if(v[mid]>target)
            right=mid;
        else
            return mid;
    }
    return -1;
}
注意，int mid=(left+right)/2的时候有可能溢出，所以可以写成int mid=left+(right-left)/2;
二分查找真正的挑战来自于输入有序数组有很多重复的元素。
如果我们需要找重复元素的第一个
int search(vector& v,int target){
    int left=0;
    int last=-1;
    int right=v.size();
    while(left         int mid=left+(right-left)/2;
        if(v[mid]             left=mid+1;
        else if(v[mid]>target)
            right=mid;
        else{
            last=mid;
            right=mid;
        }
    }
    return last;
}

还有一些变种，比如找小于某个数的第一个元素
int search(vector& v,int target){
    int left=0;
    int last=-1;
    int right=v.size();
    while(left         int mid=left+(right-left)/2;
        if(v[mid]             last=mid;
            left=mid+1;
        }
        else{
            right=mid;
        }
    }
    return last;
}