思路

二分的本质是边界。

如图，大的区间 [l, r] 被分成两个部分，红色区间和蓝色区间分别满足两种性质，此时可以使用整数二分找到红色区间的右端点和蓝色区间的左端点。

首先考虑找到红色区间的右端点。

思路：

1. mid = \frac{l + r + 1}{2}

2. 如果 mid 满足红色区间的性质，说明 mid 落在红色区间上面，下一步查找的区间就为 [mid, r]，即 l = mid 。

3. 如果 mid 满足不红色区间的性质，说明 mid 落在蓝色区间上面，因为此时 mid 已经不满足要求了，所以查找区间最右的端点是 mid - 1，下一步查找的区间就为 [l, mid - 1]，即 r = mid - 1 。
   注意：此时mid一定要补上加一

查找蓝色区间的左端点。

思路：

1. .mid = \frac{l + r}{2}

2. 如果 mid 满足蓝色区间的性质，说明 mid 落在蓝色区间上面，下一步查找的区间就为 [l, mid]，即 r = mid 。

3. 如果 mid 满足不蓝色区间的性质，说明 mid 落在红色区间上面，因为此时 mid 已经不满足要求了，所以查找区间最左的端点是 mid + 1，下一步查找的区间就为 [mid + 1, r]，即 l = mid + 1 。

模板

bool check(int x) { /* ... */ } // 检查 x 是否满足性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

例题

题目：

给定一个按照升序排列的长度为 nn 的整数数组，以及 qq 个查询。
对于每个查询，返回一个元素 kk 的起始位置和终止位置（位置从 00 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。

输入格式

• 第一行包含整数 nn 和 qq，表示数组长度和询问个数。

• 第二行包含 nn 个整数（均在 1∼100001∼10000 范围内），表示完整数组。

• 接下来 qq 行，每行包含一个整数 kk，表示一个询问元素。

输出格式

• 共 qq 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

• 如果数组中不存在该元素，则返回 -1 -1。

数据范围

• 1≤n≤1000001≤n≤100000

• 1≤q≤100001≤q≤10000

• 1≤k≤100001≤k≤10000

输入样例：

6 3
1 2 2 3 3 4
3
4
5

输出样例：

3 4
5 5
-1 -1

解答：

#include <iostream>
#include <vector>

// 找到所求元素的起始位置，即左边界，即划分为 小于x 和 大于等于x
int find_left_side(std::vector<int>& arr, int x) {
    int l = 0, r = arr.size() - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (arr[mid] >= x) {
            // 下一步从 l 到 mid
            r = mid;
        } else {
            // 下一步从 mid + 1 到 r
            l = mid + 1;
        }
    }
    return arr[l] == x ? l : -1;
}

// 找到所求元素的终止，即右边界，即划分为 小于等于x 和 大于x
int find_right_side(std::vector<int>& arr, int x) {
    int l = 0, r = arr.size() - 1;
    while (l < r) {
        int mid = (l + r + 1) / 2;
        if (arr[mid] > x) {
            r = mid - 1;
        } else {
            l = mid;
        }
    }
    return arr[l] == x ? l : -1;
}

int main() {
    int n = 0, q = 0;
    std::cin >> n >> q;
    std::vector<int> arr(n, 0);
    for (auto i = 0; i < n; i++) {
        std::cin >> arr[i];
    }
    for (auto i = 0; i < q; i++) {
        int k = 0;
        std::cin >> k;
        std::cout << find_left_side(arr, k) << " " << find_right_side(arr, k) << std::endl;
    }
    return 0;
}