【一周一算法】第五周：二分查找（Binary Search）

---

🧮 一周一个算法 · 第 5 周

二分查找（Binary Search）—— 数学视角下的对数之美

“虽然二分查找的基本思想非常简单，但细节却不仅是‘棘手’，简直是噩梦。”

—— Donald Knuth（图灵奖得主，《计算机程序设计艺术》作者）

🧭 一、引言：从“猜数字”游戏说起

你一定玩过猜数字游戏：

我心里想了一个 1 到 100 之间的数字。

你猜 50，我说“大了”；

你猜 25，我说“小了”；

你猜 37……

这个直觉性的策略，就是 二分查找。

如果你从 1 开始挨个问（线性查找），运气不好要问 100 次。

但用“折半”的方法，$\log_2 100 \approx 6.64$，最多只需 7 次 就能猜中！

前四周我们搞定了“怎么让数据有序（排序）”，这一周我们来谈谈“有序之后能干嘛（查找）”。我们将学习如何将 $O(n)$ 的暴力搜索，降维打击成 $O(\log n)$ 的优雅搜索。

🧩 二、算法思想

🧠 核心逻辑

二分查找的前提是：数据必须是有序的（单调递增或递减）。

它的核心策略是 “减而治之”（Decrease and Conquer）：

每次比较中间元素，如果不是目标值，就排除掉整整一半的搜索空间。

演示

在数组 [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] 中查找 23：

1. Range

   $$0..9$$

   : 中间值 arr[4] = 16。

   $16 < 23$，说明目标在右边。抛弃左半边。

2. Range

   $$5..9$$

   : 中间值 arr[7] = 56。

   $56 > 23$，说明目标在左边。抛弃右半边。

3. Range

   $$5..6$$

   : 中间值 arr[5] = 23。

   命中！ 返回索引 5。

⚙️ 三、代码实现与“魔鬼细节”

二分查找看似简单，但要在面试或工程中写出没有任何 Bug 的二分查找，只有 10% 的程序员能一次做对。

🚨 常见的三大坑点：

1. 循环条件：是 low < high 还是 low <= high？
2. 中点计算：(low + high) / 2 会溢出吗？
3. 边界更新：是 low = mid 还是 low = mid + 1？

💻 标准 C++ 实现（闭区间写法）

我们采用最符合直觉的 [low, high] 闭区间 写法：

#include <iostream>
#include <vector>

/**
 * 标准二分查找
 * @param nums 有序数组
 * @param target 目标值
 * @return 目标值的索引，若不存在返回 -1
 */
int binarySearch(const std::vector<int>& nums, int target) {
    int low = 0;
    int high = static_cast<int>(nums.size()) - 1; // ⚠️ 注意：闭区间

    // 坑点1：这里必须是 <=，因为 low == high 时区间内还有一个元素需要判断
    while (low <= high) {
        // 坑点2：防止 (low + high) 溢出整型范围
        // 等同于 (low + high) / 2，但更安全
        int mid = low + (high - low) / 2;

        if (nums[mid] == target) {
            return mid; // 找到目标
        } 
        else if (nums[mid] < target) {
            // 目标在右边，当前 mid 已判断过，故 +1
            low = mid + 1;
        } 
        else {
            // 目标在左边，当前 mid 已判断过，故 -1
            high = mid - 1;
        }
    }

    return -1; // 未找到
}

int main() {
    std::vector<int> arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int target = 23;
    
    int index = binarySearch(arr, target);
    if (index != -1)
        std::cout << "找到目标 " << target << " 在索引: " << index << std::endl;
    else
        std::cout << "未找到目标" << std::endl;
        
    return 0;
}

📈 四、复杂度分析（数学视角）

1️⃣ 时间复杂度：$O(\log n)$

为什么是 $\log$？

每次操作，搜索空间 $n$ 都会变成 $n/2$。

假设经过 $k$ 次比较后结束，那么：

$$\frac{n}{2^k} = 1 \implies 2^k = n \implies k = \log_2 n$$

直观感受 $O(\log n)$ 的恐怖效率：

|

| 数据规模 (n) | 线性查找 O(n) | 二分查找 O(log2n) |

| 100 | 100 次 | 7 次 |

| 1,000,000 (百万) | 100 万次 | 20 次 |

| 4,000,000,000 (四十亿) | 40 亿次 | 32 次 |

结论：在海量数据面前，二分查找几乎可以被视为“瞬间完成”。

2️⃣ 空间复杂度：$O(1)$

上述迭代版本只使用了 low, high, mid 三个变量，不需要额外的递归栈空间。

🔍 五、进阶：查找边界（Lower & Upper Bound）

标准的二分查找只能判断“有没有”。但在实际应用中，如果数组里有重复元素（如 [1, 2, 2, 2, 3]），我们往往需要找到：

• 第一个等于 target 的元素（左边界）
• 最后一个等于 target 的元素（右边界）

C++ STL 的秘密武器

C++ <algorithm> 库提供了两个极其实用的二分函数，强烈建议直接使用：

1. std::lower_bound：查找第一个 $\ge$ target 的位置。
2. std::upper_bound：查找第一个 $>$ target 的位置。

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> data = {1, 2, 4, 4, 4, 6, 8};
    
    // 寻找第一个 4
    auto it = std::lower_bound(data.begin(), data.end(), 4);
    std::cout << "第一个 4 的下标: " << (it - data.begin()) << std::endl; // 输出 2
    
    // 寻找最后一个 4 
    // upper_bound 返回第一个 >4 的位置(即6的位置)，减1就是最后一个4
    auto it_last = std::upper_bound(data.begin(), data.end(), 4);
    std::cout << "最后一个 4 的下标: " << (it_last - data.begin() - 1) << std::endl; // 输出 4
}

🧠 六、思考题与练习

1. 溢出保护：为什么 low + (high - low) / 2 能够防止溢出？它和 (low + high) / 2 在数学上等价吗？
2. 旋转数组：如果一个有序数组在某个点旋转了（例如 [4,5,6,7,0,1,2]），如何用 $O(\log n)$ 找到最小值？（LeetCode #153）
3. 答案集二分：如何计算一个数的平方根 sqrt(x)，精确到整数位，且不使用库函数？
   • 提示：答案一定在 0 到 x 之间，这个区间是“有序”的，可以二分！

🌱 七、延伸阅读

• 《编程珠玑》（Programming Pearls）第四章：详细讨论了二分查找的正确性证明。
• LeetCode 专题：
  • #704. Binary Search (基础)
  • #34. Find First and Last Position (进阶边界)
  • #69. Sqrt(x) (答案二分)

✨ 八、总结

| 指标 | 二分查找 (Binary Search) |

| 前提 | 数组必须有序 |

| 时间复杂度 | $O(\log n)$ |

| 空间复杂度 | $O(1)$ (迭代版) |

| 核心思想 | 减而治之，每次排除一半 |

| 常见坑点 | 整数溢出、无限死循环（边界更新错误） |

🧩 “二分查找教会我们： 即使面对浩瀚的数据海洋，只要世界是有序的， 我们只需几十次提问，就能找到真理。”

🔜 下周预告（第 6 周）

分治算法通论与主定理（Master Theorem） > 我们已经学了归并（分治）、快排（分治）和二分（减治）。

下周我们将站在更高的高度，用数学公式 主定理 一把梭哈，彻底搞懂所有递归算法的复杂度是怎么算出来的！