二分查找算法详解与模板总结：从原理到变体

二分查找算法详解

二分查找（Binary Search）是一种在有序数组中查找特定元素的高效算法。它的核心思想是分而治之，每次将搜索范围缩小一半。

基本原理

想象你在查英语字典找"apple"这个词：

1. 翻开字典的中间
2. 如果这一页的单词在"apple"之前，就往后翻
3. 如果这一页的单词在"apple"之后，就往前翻
4. 重复这个过程，直到找到"apple"

这就是二分查找的生活例子。

算法步骤

假设有一个升序数组 arr，要查找目标值 target：

1. 初始化左指针 left = 0，右指针 right = n-1
2. 当 left <= right 时循环：
   • 计算中间位置 mid = left + (right - left) / 2（防止整数溢出）
   • 如果 arr[mid] == target，找到目标，返回 mid
   • 如果 arr[mid] < target，说明目标在右半部分，left = mid + 1
   • 如果 arr[mid] > target，说明目标在左半部分，right = mid - 1
3. 循环结束未找到，返回 -1

代码实现

基础版本（查找精确值）

int binarySearch(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    while (left <= right) {
        // 避免 (left + right) 可能溢出
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid; // 找到目标
        } else if (nums[mid] < target) {
            left = mid + 1; // 目标在右半部分
        } else {
            right = mid - 1; // 目标在左半部分
        }
    }
    return -1; // 未找到
}

时间复杂度分析

• 时间复杂度：O(log n)
  • 每次比较后，搜索范围减半
  • 对于大小为 n 的数组，最多需要 log₂(n) 次比较
• 空间复杂度：O(1)
  • 只需要常数级别的额外空间

二分查找的变体

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

int findFirst(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            result = mid; // 记录当前位置
            right = mid - 1; // 继续向左查找
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

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

int findLast(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            result = mid; // 记录当前位置
            left = mid + 1; // 继续向右查找
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

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

int findFirstGreaterOrEqual(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) {
            right = mid - 1; // 虽然满足条件，但继续向左找更小的
        } else {
            left = mid + 1; // 当前太小，向右找
        }
    }
    return left; // left 就是第一个 >= target 的位置
}

常见应用场景

1. 有序数组的查找 - 最基础的应用
2. 求平方根 - 在 0 到 x 之间二分查找
3. 旋转数组的查找 - 如 [4,5,6,7,0,1,2] 中查找
4. 寻找峰值 - 在山峰数组中找到最大值
5. 在答案空间二分 - 如"找到最小速度使得在规定时间内完成任务"

注意事项和常见错误

1. 循环条件：left <= right vs left < right 的选择
2. 边界更新：left = mid + 1 和 right = mid - 1 要正确
3. 整数溢出：使用 mid = left + (right - left) / 2 而非 (left + right) / 2
4. 数组必须有序：二分查找的前提是有序，否则结果错误
5. 重复元素：处理重复元素时要明确需求（找第一个/最后一个）

二分查找虽然原理简单，但细节容易出错。建议多练习不同类型的题目，熟练掌握各种变体的写法。

二分算法模板总结

// 找左边
while (left < right) {
    int mid = left + (right - left) / 2;
    // 左边
    if (nums[mid] >= target) right = mid;
    // 右边
    else left = mid + 1;
}

// 找右边
while (left < right) {
    int mid = left + (right - left + 1) / 2;
    // 右边
    if (nums[mid] <= target) left = mid;
    // 左边
    else right = mid - 1;
}

实战练习题目（含链接）

二分查找（easy）
在排序数组中查找元素的第一个和最后一个位置（medium）
搜索插入位置（easy）
x 的平方根（easy）
山峰数组的峰顶（easy）
寻找峰值（medium）
搜索旋转排序数组中的最小值（medium）
0〜n-1 中缺失的数字（easy）