【打卡D6】二分法

整数二分算法模板 —— 模板题 AcWing 789. 数的范围
bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int left_search(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 right_search(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;

注意：有＋就有－
    }
    return l;
}

二分法（Binary Search）详解

二分法（Binary Search）是一种经典的 分治算法，常用于在 已排序的数组 或 区间 中查找目标值。其核心思想是通过不断将搜索区间对半分，缩小查找范围，从而 高效 地找到目标元素。二分法的时间复杂度是 O(log n)，因此在处理大规模数据时非常高效。

基本思想

二分查找的核心思路是：

1. 将待查找的区间分成两部分，根据中间元素与目标值的比较结果决定下一步搜索的区间。
2. 继续在新的一半区间内查找，不断缩小查找的范围，直到找到目标元素，或确认目标元素不在数组中。

基本步骤

1. 初始化区间：设定两个边界，通常是 左边界 l 和 右边界 r，表示当前查找的范围。
2. 计算中间位置 mid：每次计算中间位置 mid = (l + r) / 2（或者使用 mid = l + (r - l) / 2 来防止溢出）。
3. 比较中间值与目标值：
   • 如果中间值等于目标值，则 找到了目标。
   • 如果中间值大于目标值，则目标值可能在中间值的左侧，因此 将右边界 r 移动到 mid - 1。
   • 如果中间值小于目标值，则目标值可能在中间值的右侧，因此 将左边界 l 移动到 mid + 1。
4. 停止条件：当 左边界 l 不再小于右边界 r，说明找到了目标，或者目标不在数组中。

例：假设数组 a = {1, 2, 2, 3, 3, 3, 4, 5, 5}，并查询 x = 3，左边界和右边界的位置

1. 查找左边界：

   • 使用 searchleft(0, 8, 3)，通过二分查找，返回第一个 3 出现的位置，结果是 3。

2. 查找右边界：

   • 使用 searchright(0, 8, 3)，通过二分查找，返回最后一个 3 出现的位置，结果是 5。

3. 输出：

#include <algorithm>
#include <iostream>
using namespace std;

const int N = 1e5 + 10; // 定义数组大小的上限
int a[N]; // 数组，用来存储输入的已排序整数

// 左边界
int searchleft(int l, int r, int x) {
    while (l < r) {  // 当左右边界还未收敛时
        int mid = (r + l) >> 1;  // 计算中间位置
        if (a[mid] >= x) r = mid;  // 如果中间值大于等于 x，则右边界收缩
        else l = mid + 1;  // 如果中间值小于 x，则左边界收缩
    }
    return l;  // 返回左边界位置，表示第一个大于等于 x 的位置
}

// 右边界
int searchright(int l, int r, int x) {
    while (l < r) {  // 当左右边界还未收敛时
        int mid = (l + r + 1) >> 1;  // 计算中间位置，偏向右侧
        if (a[mid] <= x) l = mid;  // 如果中间值小于等于 x，则左边界收缩
        else r = mid - 1;  // 如果中间值大于 x，则右边界收缩
    }
    return r;  // 返回右边界位置，表示最后一个小于等于 x 的位置
}

int main() {
    int n, q;  // n 为数组的长度，q 为查询次数
    cin >> n >> q;  // 输入数组长度和查询次数
    for (int i = 0; i < n; i++) cin >> a[i];  // 输入已排序数组

    while (q--) {  // 循环处理每一个查询
        int x;  // 当前查询的目标数字
        cin >> x;  // 输入要查询的数字 x

        // 查找第一个大于等于 x 的位置，使用左边界二分查找
        int l = searchleft(0, n - 1, x);
        
        // 如果 l 指向的不是 x，说明数组中没有 x
        if (a[l] != x) {
            cout << "-1 -1" << endl;  // 输出 -1 -1，表示 x 不在数组中
        } else {
            // 查找最后一个小于等于 x 的位置，使用右边界二分查找
            int r = searchright(0, n - 1, x);
            // 输出左边界和右边界，即 x 的第一次和最后一次出现的位置
            cout << l << " " << r << endl;
        }
    }

    return 0;  // 返回 0，程序正常结束
}