题解 | #二分查找#

class BinarySearch 
{
public:
    int getPos(vector<int> A, int n, int val) 
    {
        int left=0,right=n-1;
        while(left<=right)
        { 
            int mid=left+(right-left)/2;
            if(A[mid]>val) right=mid-1; 
            else if(A[mid]<val) left=mid+1;
            else if(A[mid]==val) right=mid-1;   // 关键在于找到一个(此时不一定是左边界)后怎么做. 找到一个后继搜索左边(将右边界左移).此时有两种情况:1.只有一个元素, 这时候执行right=mid-1, 跳出循环, 我们判定left,不影响;2. 不止一个元素, 最后都会到有两个元素的情况-> 比如如果最后出现一个 1,3 的情况, 再循环一次就是判定 1 了, 因为mid=左边那个
        }
        if(left<0||left>=A.size())
        {
            return -1;
        }
        return A[left]=val?left:-1;
    }
};