参考文章:https://blog.csdn.net/melonyzzZ/article/details/128599307

经典的左闭右闭二分查找,即查找的范围是 [l,r]

class BinarySearch {
  public:
    int getPos(vector<int> A, int n, int val) {
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (val > A[mid]) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return (l < n && A[l] == val) ? l : -1;
    }
};

时间复杂度:O(logn)

空间复杂度:O(1)