二分查找：从原理到竞赛应用

什么是二分查找？

二分查找（Binary Search）是一种在有序数组中高效查找目标值的算法。它每次将搜索范围缩小一半，因此时间复杂度仅为 O(log n)。

前提：二分查找要求数组必须是有序的（升序或降序）。

基本原理

想象你在猜一个 1 到 100 之间的数字：

1. 你猜 50（中间值）
2. 如果告诉你"大了"，那么答案在 1-49
3. 如果告诉你"小了"，那么答案在 51-100
4. 继续在剩余范围内猜中间值

每次猜测都能排除一半的可能性，最多只需要 7 次就能猜到 1-100 中的任意数字！

基础实现

标准 binarySearch

// 在有序数组 a 中查找 target，返回下标，不存在返回 -1
int binarySearch(int a[], int n, int target) {
    int left = 0, right = n - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;  // 防止溢出
        
        if (a[mid] == target) {
            return mid;
        } else if (a[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;  // 未找到
}

为什么用 left + (right - left) / 2 而不是 (left + right) / 2？

当 left 和 right 都很大时，(left + right) 可能溢出。使用减法可以避免这个问题。

常见变种

1. 查找第一个等于目标的位置

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

2. 查找最后一个等于目标的位置

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

3. 查找第一个大于等于目标的位置

int lowerBound(int a[], int n, int target) {
    int left = 0, right = n;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        if (a[mid] >= target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;  // left 就是答案
}

4. 查找第一个大于目标的位置

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

C++ STL 中的二分查找

竞赛中推荐直接使用 STL：

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

vector<int> v = {1, 2, 4, 4, 4, 6, 7, 9};

// 查找第一个 >= target 的位置
int pos1 = lower_bound(v.begin(), v.end(), 4) - v.begin();  // 返回 2

// 查找第一个 > target 的位置
int pos2 = upper_bound(v.begin(), v.end(), 4) - v.begin();  // 返回 5

// 判断元素是否存在
bool exists = binary_search(v.begin(), v.end(), 4);  // 返回 true

// 计算 target 出现的次数
int count = upper_bound(v.begin(), v.end(), 4) - lower_bound(v.begin(), v.end(), 4);

二分答案

在竞赛中，很多题目需要"二分答案"——即二分搜索答案的范围。

经典问题：木材加工

题目：有 n 根木材，要切割出 k 根等长的木棒，求能切出的最大长度。

思路：

• 答案范围：最小可能是 1，最大可能是最长木材的长度
• 对于给定的长度 mid，计算能切出多少根
• 如果能切出 >= k 根，说明可以更长
• 否则需要更短

bool canCut(int logs[], int n, int k, long long len) {
    long long count = 0;
    for (int i = 0; i < n; i++) {
        count += logs[i] / len;
    }
    return count >= k;
}

long long maxLen(int logs[], int n, int k) {
    long long left = 1, right = *max_element(logs, logs + n);
    long long result = 0;
    
    while (left <= right) {
        long long mid = left + (right - left) / 2;
        
        if (canCut(logs, n, k, mid)) {
            result = mid;
            left = mid + 1;  // 尝试更长的
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

适用场景

二分答案适用于：

1. 答案具有单调性：如果 mid 满足条件，那么更大/更小的值也可能满足
2. 可以高效验证答案是否可行

常见题目类型：

• 求最大/最小值
• 跳石头问题
• 分数规划
• 第 K 大/小问题

实战例题

例题 1：查找范围

在有序数组中查找目标值出现的范围 [first, last]。

vector<int> searchRange(int a[], int n, int target) {
    int first = lower_bound(a, a + n, target) - a;
    int last = upper_bound(a, a + n, target) - a - 1;
    
    if (first > last) return {-1, -1};  // 不存在
    return {first, last};
}

例题 2：sqrt(x)

实现整数平方根函数。

int mySqrt(int x) {
    if (x == 0) return 0;
    
    long long left = 1, right = x;
    while (left <= right) {
        long long mid = left + (right - left) / 2;
        if (mid * mid == x) {
            return mid;
        } else if (mid * mid < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return right;  // 返回向下取整的结果
}

常见错误

1. 死循环

// 错误：left < right 的循环条件，更新时必须是 right = mid 或 left = mid + 1
while (left < right) {
    int mid = left + (right - left) / 2;
    if (a[mid] >= target) {
        right = mid - 1;  // 错误！应该是 right = mid
    } else {
        left = mid + 1;
    }
}

2. 溢出

// 错误：left + right 可能溢出
int mid = (left + right) / 2;

// 正确
int mid = left + (right - left) / 2;

3. 边界条件

忘记处理空数组、单元素数组等边界情况。

练习建议

---

核心要点：二分查找的关键是确定搜索范围和更新条件，多练习才能熟练掌握！