二分查找算法

大家好，我是老马。

今天我们一起来学习一下数组密切相关的二分查找算法。

主要知识

二分查找算法需要拆分下面几个部分：

  1. 入门介绍

  2. 题目练习（按照算法思想分类）

  3. 梳理对应的 sdk 包

  4. 应用实战

入门介绍

二分查找法（Binary Search）是算法中非常经典且高效的一种查找方法，适用于有序集合。

下面是对它的详细介绍、各种变体、实战技巧与常见坑点，适合用于 LeetCode 刷题和算法面试准备。

✅ 一、二分查找法是什么？

二分查找是一种在有序数组中查找目标值的算法，每次将搜索区间折半，从而大大减少搜索范围，时间复杂度为 O(log n)。

原理简述：

  • 给定一个有序数组 nums 和一个目标值 target。

  • 每次取中间值 mid：

    • 如果 nums[mid] == target，返回 mid。
    • 如果 nums[mid] < target，说明目标在右侧，左边界变为 mid + 1。
    • 如果 nums[mid] > target，目标在左侧，右边界变为 mid - 1。

🧠 二、标准模板代码（迭代版本）

public int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1; // 注意：right 是闭区间
    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; // 排除 mid
        } else {
            right = mid - 1; // 排除 mid
        }
    }
    return -1; // 未找到
}

🛠 三、二分查找的变种（边界查找）

在很多实战题中，我们不止要找是否存在某个数，还要找它的位置范围，比如第一个/最后一个等于某值的下标，这时候就要用下面这些变体：

1️⃣ 查找左边界（第一个等于 target 的位置）

int leftBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else { // nums[mid] >= target
            right = mid - 1;
        }
    }
    // left 是最小的满足 nums[left] >= target 的位置
    if (left < nums.length && nums[left] == target) return left;
    return -1;
}

2️⃣ 查找右边界（最后一个等于 target 的位置）

int rightBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) {
            left = mid + 1;
        } else { // nums[mid] > target
            right = mid - 1;
        }
    }
    // right 是最大的满足 nums[right] <= target 的位置
    if (right >= 0 && nums[right] == target) return right;
    return -1;
}

🧩 四、适用场景总结

场景 是否适用二分查找？
数组/区间是有序的 ✅
元素存在重复值（找边界） ✅
要找某个最小/最大满足条件的值 ✅（典型二分答案）
无序数组、链表结构 ❌（不适用）

💡 五、复杂度

类型 时间复杂度 空间复杂度
迭代式二分查找 O(log n) O(1)
递归式二分查找 O(log n) O(log n)
二分查找 + 复杂操作（如前缀和、模拟） O(log n * 每步复杂度) 依具体场景

二分查找实际有哪些应用场景？可以解决哪些实际的问题

很多人学了二分查找只会套模板、找值，却没意识到它在实际应用中非常广泛且高效，不仅能查找“值”，还能用来优化决策、搜索答案、定位边界、减少时间复杂度。

✅ 一、二分查找的本质：缩小区间、逼近答案

它的核心思想是：

每次排除一半可能性，快速逼近目标或满足条件的最优解。

所以，不只是找某个值！ 还包括：

  • 找某个值是否存在
  • 找第一个/最后一个满足条件的位置
  • 在一个值域范围内，找最小/最大可行解（“二分答案”）

🧭 二、二分查找的典型应用场景

1️⃣ ✅ 查找元素是否存在（基础场景）

  • 在有序数组中查找某个值

  • 例子：

    • LeetCode 704. 二分查找
    • 搜索插入位置（35）

2️⃣ ✅ 查找某个值的“左边界”或“右边界”

适合处理重复元素/边界条件的情况：

  • 查找某个元素第一次/最后一次出现的位置
  • 判断一个值是否是数组中第一个大于/小于目标的数

  • 例子：

    • LeetCode 34. 查找元素的第一个和最后一个位置
    • LeetCode 852. 山脉数组的峰值索引

3️⃣ ✅ “二分答案”问题（重点）

这是二分查找在实际应用中最有价值的一类场景！

📌 特征：

在某个值的范围内，寻找最小/最大满足条件的值

例子场景：

  • 最快的速度、最小的开销、最多可以安排多少任务
  • 最少的天数完成目标，最大容量满足条件
  • 通常伴随一个 check(x) 判断函数

💡 常见“二分答案”题目类型：

问题类型 描述 举例
速度最小值 珂珂吃香蕉 875. 爱吃香蕉的珂珂
分配最小值 最少完成任务所需的最大时间 1011. 在D天内送达包裹的能力

4️⃣ ✅ 旋转数组、变形数组的搜索

  • 当数组不再严格递增，但仍保有一定规律，可以通过二分定位区间

  • 例子：

    • LeetCode 33. 搜索旋转排序数组
    • LeetCode 153/154. 寻找旋转排序数组中的最小值

5️⃣ ✅ 数学与实用问题中的二分查找

这些不是数组，而是在值的范围/结果上进行二分：

实际场景 解释
开根号 二分逼近开根号结果（如精度为 1e-6）
精确计算 PI、平方根 牛顿迭代/二分逼近
分配资源 最小化最大负载（如服务器分配）
金融问题 利率估算、最小成本搜索
游戏设计 找到某参数下能通过某关的最小难度

🔁 总结：二分查找能解决哪些实际问题？

类型 能解决的问题 举例
经典查找 元素是否存在 查找、插入、定位
边界查找 第一个 ≥ x、最后一个 ≤ x 查找范围、计数
值域答案查找 最小值、最大值、最早/最晚可行解 最短时间、最大最小容量等
函数极值 峰值位置 山峰数组、局部最优
实际建模 开方、资源分配、决策优化 根号、快递分区、服务器调度

🧠 一句话总结：

二分查找不只是“查找一个数”，更是解决“范围内最优值”的一大利器，尤其适合有单调性质、上下界、或目标决策值的问题。

小结

希望本文对你有帮助，如果有其他想法的话，也可以评论区和大家分享哦。

各位极客的点赞收藏转发，是老马持续写作的最大动力！

下一节我们将开始进行相关力扣专题的练习，感兴趣的小伙伴可以关注一波，精彩内容，不容错过。

参考资料

  • 顺序查找

https://www.cnblogs.com/yw09041432/p/5908444.html

https://www.jb51.net/article/53863.htm

https://blog.csdn.net/jiandanokok/article/details/50517837

  • 二分查找

二分搜索算法

https://www.cnblogs.com/ider/archive/2012/04/01/binary_search.html