二分查找

对于单调递增序列 a : \([1, 2, 3, 3, 3, 3, 4, 5, 6]\)，若我要查找第一个 \(3\) 的下标和最后一个 \(3\) 的下标，可以使用二分查找，二分查找的时间复杂度为 \(O(log(n))\)，假设有 \(2 ^ {100} = 1267650600228229401496703205376\) 的数据，我们最多只需要 \(100\) 次就能找到目标数据，几乎约等于常数时间复杂度。

二分查找左区间

对于单调递增序列 a : \([1, 2, 3, 3, 3, 3, 4, 5, 6]\)，要查找 x 第一次出现的下标，定义一个左指针 l 右指针 r 和中间指针 mid，若 a[mid] < x 那么 l = mid + 1，这样使得左指针 l 过滤掉比目标值 x 还要小的数，l 会不断地向右靠近第一次出现的 x；若 a[mid] >= x 那么 r = mid ，这样会使得 r 过滤掉比 x 大的元素，也会不断地向左靠近最左边的 x。

#define vi vector<int>

int lfbin(vi a, int l, int r, int x)
{
    if (l > r) return -1;
    int mid = (l + r) / 2;
    while (l + 1 < r)
    {
        if (a[mid] < x) l = mid + 1;
        else r = mid;
        mid = (l + r) / 2;
    }
    if (a[l] == x) return l;
    else if (a[r] == x) return r;
    else return -1;
}

二分查找右区间

对于单调递增序列 a : \([1, 2, 3, 3, 3, 3, 4, 5, 6]\)，要查找 x 最后一次出现的下标，定义一个左指针 l 右指针 r 和中间指针 mid，若 a[mid] <= x 那么 l = mid，这样使得左指针 l 过滤掉比目标值 x 还要小的数，，也会不断地向右靠近最右边的 x；若 a[mid] > x 那么 r = mid - 1 ，这样会使得 r 过滤掉比 x 大的元素，r 会不断地向左靠近最右边的 x。

#define vi vector<int>

int rfbin(vi a, int l, int r, int x)
{
    if (l > r) return -1;
    int mid = (l + r) / 2;
    while (l + 1 < r)
    {
        if (a[mid] <= x) l = mid;
        else r = mid - 1;
        mid = (l + r) / 2;
    }
    if (a[r] == x) return r;
    else if (a[l] == x) return l;
    else return -1;
}