二分查找与变体

经典二分查找

// 在有序数组中查找 target，返回索引，不存在返回 -1
int binarySearch(const vector<int> &arr, int target) {
    int lo = 0, hi = arr.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // 防溢出
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}
// 时间 O(log n)，空间 O(1)

lower_bound / upper_bound

// 第一个 >= target 的位置
int lowerBound(const vector<int> &arr, int target) {
    int lo = 0, hi = arr.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;  // 可能 == arr.size()（没找到）
}

// 第一个 > target 的位置
int upperBound(const vector<int> &arr, int target) {
    int lo = 0, hi = arr.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] <= target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

// 使用示例
vector<int> arr = {1, 2, 2, 2, 3, 4};
lowerBound(arr, 2);  // 1  （第一个 2）
upperBound(arr, 2);  // 4  （3 的位置）
// 元素 2 的个数 = upperBound - lowerBound = 3

边界模板速查

目标	条件	lo 更新	hi 更新	返回值
第一个 >= target	arr[mid] < target	mid+1	mid	lo
第一个 > target	arr[mid] <= target	mid+1	mid	lo
最后一个 < target	arr[mid] < target	mid	mid-1	hi
最后一个 <= target	arr[mid] <= target	mid	mid-1	hi

记忆口诀：左闭右开 [lo, hi)，缩左用 mid+1，缩右用 mid。

旋转数组查找

// [4,5,6,7,0,1,2] 中查找 target
int searchRotated(const vector<int> &arr, int target) {
    int lo = 0, hi = arr.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;

        if (arr[lo] <= arr[mid]) {  // 左半有序
            if (arr[lo] <= target && target < arr[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {                     // 右半有序
            if (arr[mid] < target && target <= arr[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

二分答案

// 场景：找满足条件的最小值 / 最大值
// 例：n 本书分给 m 个人，最小化最大阅读量
bool canSplit(const vector<int> &pages, int m, int maxLoad) {
    int cnt = 1, sum = 0;
    for (int p : pages) {
        if (sum + p > maxLoad) { cnt++; sum = p; }
        else sum += p;
    }
    return cnt <= m;
}

int minMaxLoad(const vector<int> &pages, int m) {
    int lo = *max_element(pages.begin(), pages.end());
    int hi = accumulate(pages.begin(), pages.end(), 0);
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canSplit(pages, m, mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

常见陷阱

// 陷阱 1: mid 溢出
int mid = (lo + hi) / 2;           // ❌ lo+hi 可能溢出
int mid = lo + (hi - lo) / 2;      // ✅

// 陷阱 2: 死循环
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (condition) lo = mid;       // ❌ lo 不前进 → 死循环
    // 修正：lo = mid + 1;
}

// 陷阱 3: 边界条件
// lo <= hi   ← 找精确值
// lo < hi    ← 找边界/位置