二分.

int binarySearch(vector<int> a, int val) {
    int l = 0, r = a.size() - 1;
    while (l <= r) {
        int mi = l + (r - l) / 2;
        if (a[mi] < val)
            l = mi + 1;
        else if (val < a[mi])
            r = mi - 1;
        else if (val == a[mi])
            r = mi - 1; //左边界  最终返回的是 插入位置;
            // l = mi + 1; //右边界
    }
    return l;// l 左边界  return r: 右边界;
}