第46章二分查找

二分查找（Binary Search）又称折半搜索，是一种高效的查找算法，仅适用于有序序列，核心思路不断折半缩小搜索区间，将线性 $O(n)$ 查找优化为对数 $O(\log n)$ 级别。本章对应 GESP C++ 五级知识块 5：二分算法，要求掌握二分查找与二分答案（二分枚举法）。

二分查找 7 的区间收缩过程

46.1 二分查找基础原理

核心前提

数组/序列必须预先升序或降序排列；仅支持随机访问结构（数组、vector，链表无法高效二分）。

查找逻辑（升序数组）

设定左右边界 left、right；
取中间下标 mid，对比 arr[mid] 与目标值 target；
三者情况：
- 相等：找到目标，返回下标；
- arr[mid] < target：目标在右半区间，更新 left = mid + 1；
- arr[mid] > target：目标在左半区间，更新 right = mid - 1；
循环直到区间失效（left > right），代表不存在该值。

示例：有序数组 [1,3,5,7,9,11,13] 查找 7 初始区间 [0,6]，mid=3，值 5 < 7 → 左边界更新为 4；新区间 [4,6]，mid=5，值 9 > 7 → 右边界更新为 4；区间 [4,4]，mid=4，值 7，匹配成功返回下标 4。

46.2 基础二分两种实现

46.2.1 迭代实现（推荐，空间 $O(1)$ ）

// 在升序数组 arr，长度 n，查找 target，返回下标；无返回 -1
int binarySearchIterative(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1;
    while (left <= right) {
        // 避免 left+right 溢出，替代 (left+right)/2
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

46.2.2 递归实现（空间 $O(\log n)$ 递归栈）

int binarySearchRecursiveHelper(int arr[], int left, int right, int target) {
    if (left > right) {
        return -1;
    }
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        // 搜索右区间
        return binarySearchRecursiveHelper(arr, mid + 1, right, target);
    } else {
        // 搜索左区间
        return binarySearchRecursiveHelper(arr, left, mid - 1, target);
    }
}
// 入口函数
int binarySearchRecursive(int arr[], int n, int target) {
    return binarySearchRecursiveHelper(arr, 0, n - 1, target);
}

46.3 二分查找常用变体（含重复元素）

46.3.1 查找第一个等于 target 的下标

int findFirstOccurrence(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            result = mid;
            right = mid - 1; // 向左继续找更早位置
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

46.3.2 查找最后一个等于 target 的下标

int findLastOccurrence(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            result = mid;
            left = mid + 1; // 向右继续找更晚位置
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

46.3.3 查找 target 插入位置（不存在返回插入下标）

int searchInsertPosition(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

46.4 复杂度分析

时间复杂度：最坏/平均 $O(\log n)$ ，最好 $O(1)$ （mid 直接命中）
空间复杂度：迭代 $O(1)$ ；递归 $O(\log n)$ （递归调用栈深度）

46.5 使用前提与注意事项

序列必须有序；无序数组无法二分，需先排序（排序 $O(n\log n)$ ）；
避免 (left + right) / 2 溢出，统一使用 left + (right - left) / 2；
循环条件 left <= right 不可简写为 <，会漏掉边界元素；
更新边界必须 mid ± 1，否则区间无法收缩，出现死循环；
降序数组需反转比较逻辑；
浮点数二分需设置精度阈值判断终止。

46.6 C++ 标准库二分工具

<algorithm> 内置二分函数，仅适用于升序有序容器：

binary_search(begin, end, val)：返回 bool，判断是否存在
lower_bound(begin, end, val)：返回第一个 $\ge$ val 的迭代器
upper_bound(begin, end, val)：返回第一个 $>$ val 的迭代器

示例代码：

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

int main() {
    int arr[] = {1, 3, 5, 7, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 7;
    bool exist = binary_search(arr, arr + n, target);
    auto itLow = lower_bound(arr, arr + n, target);
    auto itHigh = upper_bound(arr, arr + n, target);
    int idxLow = itLow - arr;
    int idxHigh = itHigh - arr;
    cout << "第一个7下标：" << idxLow << endl;
    cout << "7之后第一个元素下标：" << idxHigh << endl;
    return 0;
}

46.7 二分答案（二分思想拓展）

核心思想

不直接查找数组元素，而是二分答案区间，通过 check() 函数判断当前 mid 是否满足条件，不断收缩区间求最优解。适用于满足单调性的最值类题目。

两类模板

求满足条件最大值

// condition(mid)：mid 符合条件返回 true
int findMax(int minVal, int maxVal) {
    int left = minVal, right = maxVal;
    while (left < right) {
        int mid = left + (right - left + 1) / 2; // +1 防止死循环
        if (condition(mid)) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

求满足条件最小值

int findMin(int minVal, int maxVal) {
    int left = minVal, right = maxVal;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (condition(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

适用场景

最大化最小值、最小化最大值；
分段、切割、分配类最优解；
存在单调性的判定类问题。

复杂度

单次二分 $O(\log(\text{答案范围}))$ ，总复杂度 $O(\log M \times f)$ ， $f$ 为 check 函数耗时。

46.8 选择题练习

二分查找能够高效工作的前提是： A. 数组元素互不相同 B. 数组已排序（有序） C. 数组长度为 2 的幂 D. 使用链表存储

查看答案
答案：B。二分查找依赖"中间值与目标比较后舍弃一半"的性质，必须以有序为前提；链表不支持 $O(1)$ 随机访问，不适合二分。
在升序数组 [2,4,6,8,10] 中二分查找 8，比较的中间元素依次是（下标从 0 起）： A. 6, 10, 8 B. 6, 8 C. 2, 6, 8 D. 10, 6, 8

查看答案
答案：A。mid=2 值 6 < 8 → 右半 [3,4]；mid=4 值 10 > 8 → 左半 [3,3]；mid=3 值 8 命中。比较顺序：6、10、8。
为避免 left + right 溢出，计算中点应写为： A. (left + right) / 2 B. left + (right - left) / 2 C. (right - left) / 2 D. left / 2 + right / 2

查看答案
答案：B。left + (right - left) / 2 等价且不溢出；当 left、right 都很大时 A 会溢出。
二分查找（迭代版）的平均时间复杂度是： A. $O(n)$ B. $O(\log n)$ C. $O(n \log n)$ D. $O(1)$

查看答案
答案：B。每次折半，最多比较 $\log_2 n$ 次。
二分答案（二分枚举法）常用于解决： A. 无序数组查找 B. 满足单调性的最值/判定类问题 C. 字符串匹配 D. 图的遍历

查看答案
答案：B。当答案具有单调性时，可在答案区间上二分并用 check() 判定，典型如"最大化最小值"。