二分查找

概览

二分查找的核心思想：利用单调性，每次将搜索范围缩小一半，从而在 O(log n) 时间内解决问题。它不仅适用于有序数组的精确查找，也可用于边界查找、旋转数组搜索，以及对答案值域二分解决「最小化最大值」类优化问题。

核心前提：单调谓词

存在某个分界点，左侧全为 false，右侧全为 true（或反之）。只要满足这个条件，就可以使用二分查找——不要求数组有序，只要谓词单调即可。

两种模板对比

防溢出中点计算

永远使用 mid = lo + (hi - lo) / 2，而非 (lo + hi) / 2。当 lo + hi > INT_MAX 时后者溢出为负数，导致死循环。

int mid = lo + (hi - lo) / 2;   // ✅ overflow-safe
int mid = (lo + hi) / 2;        // ❌ can overflow when lo + hi > INT_MAX

复杂度

经典二分

在已排序数组中查找目标值，返回下标；不存在则返回 -1。使用 while (lo <= hi) 闭区间模板。

核心思想

维护循环不变量：若 target 存在，则它必在 [lo, hi] 闭区间内。每次检查中点 mid：命中则返回；target 在右侧则 lo = mid+1；target 在左侧则 hi = mid-1。lo > hi 时区间为空，说明不存在。

步骤

1. 初始化 lo = 0，hi = n - 1（闭区间，hi 包含最后一个元素）
2. 计算 mid = lo + (hi - lo) / 2（防溢出）
3. 若 nums[mid] == target，返回 mid
4. 若 nums[mid] < target，目标在右半段，令 lo = mid + 1
5. 若 nums[mid] > target，目标在左半段，令 hi = mid - 1
6. lo > hi 时循环退出，返回 -1（未找到）

C++ 实现

int binarySearch(vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;   // overflow-safe
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) lo = mid + 1;
        else                         hi = mid - 1;
    }
    return -1;   // not found
}

复杂度

常见错误

边界二分

查找目标值的最左或最右出现位置，处理重复元素。统一使用 while (lo < hi) 模板，hi 取 n（开区间）。

左边界（Lower Bound）

找第一个 >= target 的下标。即 C++ std::lower_bound 的语义。若所有元素 < target，返回 n。

步骤（左边界）

1. 初始化 lo = 0，hi = n（hi 是开区间，超出末尾）
2. 计算 mid = lo + (hi - lo) / 2
3. 若 nums[mid] < target，目标在右侧，令 lo = mid + 1
4. 否则（nums[mid] >= target），收缩上界 hi = mid
5. 退出时 lo == hi，即为第一个 >= target 的下标

// First index where nums[i] >= target  (std::lower_bound semantics)
int lowerBound(vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size();  // hi = n (open interval)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < target) lo = mid + 1;
        else                    hi = mid;      // nums[mid] >= target: keep mid
    }
    return lo;  // first index >= target (== n if all elements < target)
}

右边界（Upper Bound）

找第一个 > target 的下标，即 C++ std::upper_bound 的语义。该位置减 1 是最后一个 <= target 的下标。

步骤（右边界）

1. 初始化 lo = 0，hi = n
2. 计算 mid = lo + (hi - lo) / 2
3. 若 nums[mid] <= target，令 lo = mid + 1
4. 否则（nums[mid] > target），收缩上界 hi = mid
5. 退出时 lo - 1 是最后一个 <= target 的下标

// First index where nums[i] > target  (std::upper_bound semantics)
int upperBound(vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] <= target) lo = mid + 1;  // note: <= (not <)
        else                     hi = mid;
    }
    return lo;  // lo - 1 is last index <= target
}

// Count occurrences in O(log n):
// count(target) = upperBound(target) - lowerBound(target)

统计出现次数

count(target) = upperBound(target) − lowerBound(target)，即两个边界下标之差。时间 O(log n)，远优于线性扫描。

常见错误

旋转数组二分

在经过旋转的有序数组中查找目标值（LeetCode 33）。数组被旋转后仍有一个性质：每次二分后，[lo, mid] 和 [mid, hi] 中必有一段是完全有序的。

核心思想

通过比较 nums[lo] 与 nums[mid] 判断哪半段有序：若 nums[lo] <= nums[mid]，则左半段有序；否则右半段有序。在有序半段中用普通范围检查判断 target 是否在其中，从而决定丢弃哪半段。

步骤

1. 使用 while (lo <= hi) 模板，初始 lo=0, hi=n-1
2. 若 nums[mid] == target，返回 mid
3. 若 nums[lo] <= nums[mid]（左半段有序）
4. → 若 nums[lo] <= target < nums[mid]，令 hi = mid - 1（target 在左半）
5. → 否则令 lo = mid + 1（target 在右半）
6. 若左半段无序（则右半段 [mid, hi] 有序）
7. → 若 nums[mid] < target <= nums[hi]，令 lo = mid + 1（target 在右半）
8. → 否则令 hi = mid - 1（target 在左半）

C++ 实现

int searchRotated(vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;

        if (nums[lo] <= nums[mid]) {          // left half [lo, mid] is sorted
            if (nums[lo] <= target && target < nums[mid])
                hi = mid - 1;                 // target in left half
            else
                lo = mid + 1;                 // target in right half
        } else {                              // right half [mid, hi] is sorted
            if (nums[mid] < target && target <= nums[hi])
                lo = mid + 1;                 // target in right half
            else
                hi = mid - 1;                 // target in left half
        }
    }
    return -1;
}

注意事项

答案空间二分

不对数组下标二分，而是对答案的值域二分。适用于「最小化最大值」「最大化最小值」类优化问题。

核心思想

设计一个单调谓词 feasible(x)：x 满足约束则返回 true，否则返回 false。随着 x 增大，feasible 从 false 变为 true（最小化问题）或从 true 变为 false（最大化问题）。在答案值域 [lo, hi] 上二分找到这个分界点。

通用步骤（最小化问题）

1. 确定答案值域 [lo, hi]（如最小速度为 1，最大速度为 max(piles)）
2. 定义 feasible(mid)：判断答案为 mid 时是否能满足约束
3. 若 feasible(mid) 为 true，答案可能更小，收缩 hi = mid
4. 若 feasible(mid) 为 false，答案需更大，收缩 lo = mid + 1
5. 退出时 lo == hi，即为最小可行答案

C++ 示例（875. 珂珂吃香蕉）

// LC 875 — Koko Eating Bananas
// Given piles of bananas and h hours, find minimum eating speed.

bool canFinish(vector<int>& piles, long long h, long long speed) {
    long long hours = 0;
    for (int p : piles) hours += (p + speed - 1) / speed;  // ceil(p/speed)
    return hours <= h;
}

int minEatingSpeed(vector<int>& piles, int h) {
    int lo = 1, hi = *max_element(piles.begin(), piles.end());
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canFinish(piles, h, mid)) hi = mid;  // feasible, try smaller
        else                          lo = mid + 1;
    }
    return lo;
}

常见变体

常见错误

LeetCode 题型

按模板分类的高频二分查找题目。

经典二分

边界二分

旋转数组

答案空间二分