题解 | 二分查找

class BinarySearch {
public:
    int getPos(vector<int> A, int n, int val) {
        // write code here
        //algorithm中有二分查找法的lower_bound可以找到第一个大于等于目标值的位置
        //upper_bound可以找到第一个大于目标值的位置
        // auto it=lower_bound(A.begin(),A.end(),val);
        // if(it!=A.end())
        //     return it-A.begin();
        // return -1;

        //自己实现二分查找
        //定义查找起始指针和末尾指针
        int left=0;int right=n-1;//查找范围[left,right]
        //每次与范围中间值比较，直到查找范围为空
        while(left<=right)
        {
            //与中间值比较
            int mid=left+(right-left)/2;//防溢出写法
            if(A[mid]<val)
                left=mid+1;
            else
                right=mid-1;
            //可以确保left左边都是小于val的，right右边都是大于等于val的
        }
        //循环结束后，left或者right+1就是第一个大于等于val的位置
        return left;
    }
};