Lesson 40: 二分查找

练习任务

难度：中【重点】【面试高频】

实现迭代二分查找 binary_search(arr, n, target)，在有序数组中查找目标值，找到返回索引，未找到返回 -1。

int binary_search(int arr[], int n, int target);

验证用例：

输入 "1 3 5 7 9 11" + "\n5\n"  → 2
输入 "1 3 5 7 9 11" + "\n6\n"  → -1
输入 "1"            + "\n1\n"  → 0

二分查找是算法面试中出现频率最高的题目之一。Jon Bentley 在《编程珠玑》中提到，他让 100 多位专业程序员写二分查找，90% 写出的代码有 bug——多数栽在三个经典陷阱上。这不到 10 行的代码，几十年来一直是区分"背代码"和"真理解"的试金石。

提示：二分查找不到 10 行，但三个陷阱各藏杀机。写完代码后，问自己三个问题：(1) mid 会溢出吗？(2) 循环条件带等号了吗？(3) lo 和 hi 更新时加 1/减 1 了吗？如果能自信地回答这三个问题，你才真正学会了二分查找。

核心知识点

O(log n) 对数时间 — 每轮搜索空间减半，n / 2^k = 1 → k = log₂n。n=10^9 时最多只需 30 次比较，是算法效率的标杆
有序前提不可违背 — arr[mid] < target 能推断 target 在右侧，仅当数组有序；无序数组必须用线性查找，二分结果不确定
陷阱 1: mid 溢出 — mid = (lo + hi) / 2 在大数组时 lo+hi 超过 INT_MAX 导致溢出为负数，正确写法 mid = lo + (hi - lo) / 2。Java Arrays.binarySearch 的 JDK-5045582 bug 潜伏了 9 年
陷阱 2: 循环条件 <= — while (lo <= hi) 的等号保证单元素搜索空间不被漏判；写成 lo < hi 会在 lo==hi 时直接退出，数组 [5] 中查找 5 返回 -1
陷阱 3: 指针更新 mid ± 1 — lo = mid + 1 和 hi = mid - 1 保证搜索空间严格缩小；写成 lo = mid 当 lo=0, hi=1, mid=0 时 lo 不变 → 死循环
Bentley《编程珠玑》轶事 — 90% 的专业程序员写不对二分查找，三个陷阱是区分"背代码"和"真理解"的标尺。二分查找是软件工程中"看起来简单，写对极难"的最佳案例
lower_bound 变体 — 找"第一个 ≥ target"的位置。与标准二分的三个差异：hi = n（而非 n-1）、while (lo < hi)（而非 <=）、hi = mid（而非 mid-1）。这些差异都源于目标从"精确匹配"变为"找左边界"
旋转有序数组二分 — 如 [4,5,6,7,0,1,2]，两种策略：(1) 两次二分找到旋转点再搜索，(2) 每次判断 mid 落在哪一侧有序段，再决定搜索方向。本质仍是每次排除一半

代码框架

40_binary_search.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* 迭代二分查找：在大小为 n 的有序数组 arr 中查找 target */
int binary_search(int arr[], int n, int target) {
    /* 初始化搜索范围：lo = 0, hi = n - 1 */


    /* while (lo <= hi) — 等号很重要！考虑只有 1 个元素时的情况 */


    /* 计算中点：mid = lo + (hi - lo) / 2
     * 为什么不用 (lo + hi) / 2？→ 避免整数溢出 */


    /* 比较 arr[mid] 和 target：
     *   等于 → 找到了，返回 mid
     *   小于 → target 在右边，lo = mid + 1
     *   大于 → target 在左边，hi = mid - 1 */


    /* 循环结束仍未找到 → 返回 -1 */

}

int main(void) {
    char line[1024], tline[32];
    fgets(line, sizeof(line), stdin);
    fgets(tline, sizeof(tline), stdin);

    int arr[1024], n = 0, target;
    char *tok = strtok(line, " \n");
    while (tok) {
        arr[n++] = atoi(tok);
        tok = strtok(NULL, " \n");
    }
    sscanf(tline, "%d", &target);

    printf("%d\n", binary_search(arr, n, target));
    return 0;
}

骨架中的核心提示：

lo = 0, hi = n - 1 初始化搜索范围为整个数组
mid = lo + (hi - lo) / 2 等价于 (lo + hi) / 2 但防溢出
while (lo <= hi) 的等号确保单元素数组也能进入循环
找到立即返回 mid，未找到返回 -1

TIP

先不要往下翻看参考解答。试着填写骨架中 // 在这里... 标记的部分，然后问自己三个问题来验证：mid 会溢出吗？循环条件带等号了吗？指针更新加了 ±1 吗？如果任何一个问题的答案是"不确定"，请仔细阅读下面的深度讲解。

深度讲解

1. O(log n) 对数时间与有序前提

1.1 "二分"的含义

二分查找的核心假设：数组有序。为什么有序是必须的？因为每次比较 arr[mid] 与 target 后，需要推断 target 在左半还是右半。如果数组无序，arr[mid] < target 不能推出 target 一定在右侧——它可能散布在任意位置。

有序数组 [1, 3, 5, 7, 9, 11]，查找 5:

第1轮: lo=0, hi=5, mid=2 → arr[2]=5 == target → 找到!
┌───┬───┬───┬───┬───┬───┐
│ 1 │ 3 │ 5 │ 7 │ 9 │11 │    只比较 1 次! (线性查找需要 3 次)
└────┴───┴───┴───┴───┴───┘
  ↑        ↑          ↑
 lo=0    mid=2       hi=5

查找 9:
第1轮: lo=0, hi=5, mid=2 → arr[2]=5 < 9 → lo=3（丢弃左半）
第2轮: lo=3, hi=5, mid=4 → arr[4]=9 == target → 找到!

为什么叫"二分"？ — 每次比较后，搜索空间减半：n → n/2 → n/4 → ... → 1。经过 k 轮后，n / 2^k = 1，所以 k = log₂n。

1.2 线性 vs 二分力觉对比

n=1000:   线性平均 500 次比较, 二分最多 10 次 (2^10=1024)
n=10^6:   线性平均 50 万次,     二分最多 20 次 (2^20≈10^6)
n=10^9:   线性平均 5 亿次,      二分最多 30 次 (2^30≈10^9)

这就是 O(n) 与 O(log n) 的鸿沟。当数据量增长 1000 倍，线性查找慢 1000 倍，而二分查找只多花约 10 次比较。二分查找是对数复杂度的最佳示范。

1.3 有序前提不能违背

disorder_demo.c

// 无序数组 [5, 1, 9, 3, 7, 11]，查找 1
// 第1轮: mid=2, arr[2]=9 > 1 → hi=mid-1=1
// 但 1 在 arr[1]！如果 hi 收缩到左侧，正好包含了 1 —— 纯属巧合

// 无序数组 [5, 1, 9, 3, 7, 11]，查找 3
// 第1轮: mid=2, arr[2]=9 > 3 → hi=mid-1=1
// 3 在 arr[3]（右侧），但搜索被限制在 [0..1] → 找不到！

结论：无序数组中的二分查找结果是不确定的——有时碰巧找到，有时找不到。只有数组有序时，arr[mid] < target 才能逻辑上保证 target 在右侧。

WARNING

忘记"数组有序"这个前提是二分查找最常见的概念性错误。在没有排序保障的场景中，请使用线性查找。

2. 陷阱 1：mid 计算溢出（最隐蔽的 bug）

2.1 错误写法与正确写法

/* ❌ 错误：lo+hi 可能超过 INT_MAX */
int mid = (lo + hi) / 2;

/* ✅ 正确：hi-lo 永远不会溢出 */
int mid = lo + (hi - lo) / 2;

两个写法在数学上等价：(lo+hi)/2 = lo + (hi-lo)/2。但前者先加后除——加法可能溢出——后者先减后除，hi - lo 因为 lo ≤ hi（搜索空间内）所以永远不会为负，自然也不会溢出。

2.2 溢出过程逐帧还原（32 位 int，INT_MAX = 2147483647）

lo = 1500000000, hi = 2000000000

错误路径:
  (lo + hi)     = 1500000000 + 2000000000
                = 3500000000
                > 2147483647 (INT_MAX)     → 溢出!
  3500000000 在 32 位有符号 int 中的二进制:
    1101 0000 1001 1010 0110 0000 0000 0000
  → 最高位是 1，被解释为负数: -794967296
  (-794967296) / 2 = -397483648 → mid 是负数!

正确路径:
  (hi - lo)     = 2000000000 - 1500000000
                = 500000000                 → 安全! 远小于 INT_MAX
  lo + (hi-lo)/2 = 1500000000 + 250000000
                = 1750000000               → 正确! ✓

2.3 Java Arrays.binarySearch 的 JDK-5045582 Bug

这个 bug 不是理论推演——它就真实存在于 Java 标准库中，潜伏了 9 年（2006 年才修复）：

Bug ID: JDK-5045582
影响函数: java.util.Arrays.binarySearch(int[], int)
触发条件: 数组长度超过约 10 亿（lo + hi > INT_MAX）
症状: mid 计算为负值，ArrayIndexOutOfBoundsException 或错误结果
修复: 将 (low + high) / 2 改为 (low + high) >>> 1（无符号右移）

Google 的 TimSort 实现也在 2015 年因类似溢出导致崩溃。这类 bug 的共同特征：小数据测试永远遇不到，只有大规模生产环境才暴露。

CAUTION

mid = (lo + hi) / 2 的溢出 bug 是二分查找中最阴险的错误——它在你调试的小数组上永远正确，但一到生产环境的大数组就崩溃。永远用 mid = lo + (hi - lo) / 2，把这个写法变成肌肉记忆。

3. 陷阱 2：循环条件 `lo <= hi` 的 `<=` 号

3.1 两种写法的行为差异

写法	lo == hi 时的行为	后果
`while (lo <= hi)` ✅	进入循环	正确处理单元素搜索空间
`while (lo < hi)` ❌	直接退出	漏判单元素情况！

3.2 具体反例：单元素数组

数组 [5]，查找 5:

while (lo <= hi):
  lo=0, hi=0 → 0 <= 0 成立 → 进入循环
  → mid = 0 + (0-0)/2 = 0
  → arr[0] == 5 → return 0 ✓

while (lo < hi):
  lo=0, hi=0 → 0 < 0 不成立 → 不进入循环
  → return -1 ✗ (明明有 5！)

3.3 `<=` 的数学语义

while (lo <= hi) 的 <= 表示搜索空间至少包含一个元素时继续：

lo == hi → 搜索空间包含 1 个元素 → 仍需检查 → 进入循环
lo > hi → 搜索空间为空 → 可以退出

这正好对应了"左闭右闭"区间 [lo, hi] 的语义——区间非空当且仅当 lo ≤ hi。

lo 和 hi 的关系态态图:

  lo < hi:  [lo ... hi]  多元素 → 继续二分
  lo == hi: [lo]         单元素 → 仍需检查! (这是 <= 的价值)
  lo > hi:  空区间        无元素 → 退出循环

IMPORTANT

while (lo <= hi) 的 <= 不是可选的风格偏好——它是正确性的硬要求。少一个等号，就等于告诉程序"忽略只有 1 个元素的搜索空间"。这在算法正确性上是不可接受的。

4. 陷阱 3：指针更新 `lo = mid + 1` 防止死循环

4.1 错误写法导致的死循环

/* ❌ 错误: 死循环! */
if (arr[mid] < target)
    lo = mid;      // lo 不前进！

/* ✅ 正确: lo 必然前进 */
if (arr[mid] < target)
    lo = mid + 1;  // lo 至少前进 1

4.2 死循环逐帧跟踪

数组 [1, 3]，查找 5（不存在），使用 lo = mid（错误写法）:

初始: lo=0, hi=1
第1轮: mid = 0+(1-0)/2 = 0
       arr[0]=1 < 5 → lo = mid = 0       ← lo 没变！
第2轮: mid = 0+(1-0)/2 = 0
       arr[0]=1 < 5 → lo = mid = 0       ← lo 还是 0！
第3轮: 完全一样 → 无限循环！

正确写法 (lo = mid + 1):
初始: lo=0, hi=1
第1轮: mid = 0+(1-0)/2 = 0
       arr[0]=1 < 5 → lo = mid + 1 = 1
第2轮: mid = 1+(1-1)/2 = 1
       arr[1]=3 < 5 → lo = mid + 1 = 2
第3轮: lo=2 > hi=1 → 退出 → return -1 ✓

4.3 为什么 `lo = mid` 在 `lo + 1 == hi` 时会死循环？

当搜索空间只剩 2 个元素 [lo, lo+1] 时，mid = lo + (hi-lo)/2 = lo + 0 = lo。如果条件走 lo = mid 分支，lo 保持原值，搜索空间没有缩小——下轮循环状态完全一样，形成死循环。

关键场景: lo=0, hi=1
  mid = 0 + (1-0)/2 = 0 + 0 = 0  → mid 就是 lo!

  if (arr[mid] < target)       arr[mid] 比 target 小
      lo = mid;                 lo 不变 → 死循环!

  if (arr[mid] > target)       另一种情况
      hi = mid;                 如果写成 hi = mid → hi 不变 → 也是死循环!

这就是为什么 +1 和 -1 都是必需的：

lo = mid + 1 — lo 向右至少移动 1 步，搜索空间变小
hi = mid - 1 — hi 向左至少移动 1 步，搜索空间变小

WARNING

在二分查找中，lo = mid 和 hi = mid 都可能导致死循环。唯一的正确做法是 lo = mid + 1 和 hi = mid - 1。±1 不是优化——它是算法能终止的保证。

4.4 完整的三陷阱对照表

陷阱	错误写法	正确写法	触发条件	后果
mid 溢出	`(lo+hi)/2`	`lo+(hi-lo)/2`	lo+hi > INT_MAX	mid 为负数，数组越界
循环条件	`while(lo<hi)`	`while(lo<=hi)`	lo==hi（单元素）	漏判该元素
指针更新	`lo=mid`	`lo=mid+1`	lo+1==hi, lo 分支	死循环

5. 溢出具体数值演示——lo=1.5e9, hi=2e9

5.1 数值轨迹完整推演

平台: 32 位 int, INT_MAX = 2147483647, sizeof(int)=4

lo = 1500000000 (1.5 × 10^9)
hi = 2000000000 (2.0 × 10^9)

═══════════════════════════════════════════════════════
错误计算: int mid = (lo + hi) / 2
═══════════════════════════════════════════════════════

Step 1: lo + hi 计算
  1500000000 + 2000000000 = 3500000000

Step 2: 3500000000 在有符号 32 位 int 中的表示
  3500000000 的 32 位二进制:
  ┌─┬───────────────────────────────┐
  │1│101 0000 1001 1010 0110 0000 0000│ = 0xD09A6000
  └─┴───────────────────────────────┘
   ↑
  符号位 = 1 → 负数

  按补码反求真值:
  取反: 0010 1111 0110 0101 1001 1111 1111
  加 1: 0010 1111 0110 0101 1010 0000 0000 = 794967296
  所以 0xD09A6000 表示 -794967296

Step 3: 除法
  (-794967296) / 2 = -397483648

Step 4: mid 作为索引
  int mid = -397483648;
  arr[mid] → 访问 arr[-397483648] → 未定义行为/崩溃！

═══════════════════════════════════════════════════════
正确计算: int mid = lo + (hi - lo) / 2
═══════════════════════════════════════════════════════

Step 1: hi - lo
  2000000000 - 1500000000 = 500000000  ✓ 远小于 INT_MAX

Step 2: 除法
  500000000 / 2 = 250000000           ✓ 安全!

Step 3: 加法
  1500000000 + 250000000 = 1750000000 ✓ 正确! < INT_MAX

5.2 为什么 `(hi - lo)` 永不溢出？

在二分查找的循环不变式中，始终有 0 ≤ lo ≤ hi ≤ n-1——搜索空间在数组范围内。因此：

hi - lo ≤ hi ≤ n - 1 ≤ INT_MAX

即 hi - lo 的最大值 = 数组长度 - 1，永远不超过 INT_MAX

NOTE

hi - lo 不溢出是因为它被循环不变式保证。而 lo + hi 是两个各接近 INT_MAX 的数的和，极易超过 INT_MAX。这是二分查找中最经典的"数学等价但工程不等价"的例子。

6. Bentley《编程珠玑》轶事——"90% 的专家写不对"

6.1 原文轶事

Jon Bentley 在《Programming Pearls》（《编程珠玑》）第 4 章中写道：

"I've assigned this problem in courses at Bell Labs and IBM. Professional programmers had a couple of hours to write the binary search function; they were allowed to use the language of their choice and any reference materials. 90% of the programmers found bugs in their programs."

他在贝尔实验室和 IBM 让专业程序员写二分查找——可以用任何语言、查任何资料、花几个小时——结果 90% 的代码有 bug。

6.2 为什么 90% 的人都栽了？

二分查找"看起来简单"——不到 10 行代码，小学三年级就懂的"猜数字"游戏。但工程实现中有三个需要精确理解而非记忆的细节：

┌─────────────────────────────────────────────────────┐
│ 「背代码」式的理解                              │
│                                                     │
│  int binary_search(...) {                           │
│    int lo = 0, hi = n-1;                            │
│    while (lo <= hi) {                               │
│      int mid = lo + (hi-lo)/2;                      │
│      if (arr[mid] == target) return mid;            │
│      if (arr[mid] < target) lo = mid + 1;            │
│      else hi = mid - 1;                              │
│    }                                                 │
│    return -1;                                        │
│  }                                                   │
│                                                     │
│  能默写 ≠ 能解释:                                    │
│  为什么是 <= 不是 < ？ → "书上这么写的"           │
│  为什么是 lo+(hi-lo)/2？ → "防溢出，但不知道为什么"  │
│  为什么是 mid+1？      → "不加 1 也行吧？"          │
└─────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────┐
│ 「真理解」式的理解                              │
│                                                     │
│  <=  → "左闭右闭区间 [lo, hi] 非空当且仅当 lo≤hi"   │
│  lo+(hi-lo)/2 → "hi-lo 由循环不变式保证不溢出"       │
│  mid+1 → "lo=mid 在 lo+1==hi 时 lo 不变 → 死循环"   │
│                                                     │
│  → 能画出每种错误写法导致崩溃的具体场景              │
│  → 能说出每个细节的取舍理由                          │
└─────────────────────────────────────────────────────┘

6.3 工程启示

Bentley 的发现不仅是轶事——它揭示了软件工程中的核心真相：代码长度 ≠ 代码简单度。最危险的 bug 往往藏在最短的函数里，因为：

表面简单导致轻视 — 不认真思考边界条件
测试盲区 — 小数据测试永远触发不了溢出 bug
"背代码"文化 — 只记模式不记原理

三分查找——二分是分治（Divide & Conquer）的原始操作。在后续的 Lesson 41: 快速排序中，分区的过程本质上就是对有序边界做类似二分的定位——二分查找是学习分治算法的第一步。

7. lower_bound 变体：找第一个 ≥ target 的位置

7.1 标准二分 vs lower_bound

标准二分查找找"等于 target 的任意一个位置"。lower_bound 找"第一个 ≥ target"的位置——这是 C++ STL 中 std::lower_bound 的语义。

数组 [1, 3, 3, 5, 7]:

binary_search(arr, 6, 3)     → 可能返回 1 或 2（不确定）
binary_search(arr, 6, 4)     → 返回 -1（不存在等于 4 的元素）

lower_bound(arr, 6, 3)       → 返回 1（第一个 ≥ 3 的位置）
lower_bound(arr, 6, 4)       → 返回 3（第一个 ≥ 4 的位置 = arr[3]=5）
lower_bound(arr, 6, 8)       → 返回 6 = n（所有元素都 < 8）
lower_bound(arr, 6, 0)       → 返回 0（所有元素都 ≥ 0）

7.2 lower_bound 的三个核心差异

差异点	标准二分	lower_bound	原因
hi 初值	`n-1`	`n`	可能返回 n（所有元素都 < target）
循环条件	`while (lo <= hi)`	`while (lo < hi)`	退出时 lo==hi = 答案，无需额外判断
hi 更新	`hi = mid - 1`	`hi = mid`	mid 本身可能是答案，不能跳过

7.3 lower_bound 完整实现

lower_bound.c

/* 返回第一个 >= target 的元素索引
 * 如果所有元素都 < target，返回 n
 * 前提: arr 有序 */
int lower_bound(int arr[], int n, int target) {
    int lo = 0, hi = n;              // hi = n（不是 n-1）
    while (lo < hi) {                // lo < hi（不是 <=）
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] < target)
            lo = mid + 1;            // arr[mid] 太小?一定不是答案
        else
            hi = mid;                // arr[mid] >= target, mid 可能是答案
    }
    return lo;                       // lo == hi = 第一个 >= target 的位置
}

7.4 lower_bound 循环不变式详解

循环不变式:
  - [0, lo):  所有元素 < target（已确定不满足条件）
  - [lo, hi): 未确定的区间
  - [hi, n):  所有元素 >= target（已确定满足条件，但不一定是最左）

初始: lo=0, hi=n → [0, n) 全部未确定 ✓

每次迭代 mid = lo + (hi - lo) / 2:
  情况 A: arr[mid] < target
    → arr[lo..mid] 全部 < target（有序！）
    → lo = mid + 1 → [0, lo) = 已确定 < target ✓

  情况 B: arr[mid] >= target
    → arr[mid..hi-1] 全部 >= target（有序！）
    → hi = mid → [hi, n) = 已确定 >= target ✓
    → 但 mid 可能是 ANS → 不能 hi = mid - 1

终止: lo == hi → [0, lo) 全部 < target, [lo, n) 全部 >= target
  → lo 就是第一个 >= target 的位置 ✓

7.5 lower_bound 逐步跟踪

arr = [1, 3, 3, 5, 7], n=5, target=3

初始: lo=0, hi=5
轮1: mid=2, arr[2]=3 >= 3 → hi=mid=2       [lo=0, hi=2]
轮2: mid=1, arr[1]=3 >= 3 → hi=mid=1       [lo=0, hi=1]
轮3: mid=0, arr[0]=1 < 3  → lo=mid+1=1     [lo=1, hi=1]
退出: lo=1 == hi=1 → 返回 1 ✓

arr = [1, 3, 3, 5, 7], n=5, target=4

初始: lo=0, hi=5
轮1: mid=2, arr[2]=3 < 4  → lo=mid+1=3     [lo=3, hi=5]
轮2: mid=4, arr[4]=7 >= 4 → hi=mid=4       [lo=3, hi=4]
轮3: mid=3, arr[3]=5 >= 4 → hi=mid=3       [lo=3, hi=3]
退出: lo=3 == hi=3 → 返回 3 ✓ (arr[3]=5, 第一个 ≥ 4)

arr = [1, 3, 3, 5, 7], n=5, target=8

初始: lo=0, hi=5
轮1: mid=2, arr[2]=3 < 8  → lo=mid+1=3     [lo=3, hi=5]
轮2: mid=4, arr[4]=7 < 8  → lo=mid+1=5     [lo=5, hi=5]
退出: lo=5 == hi=5 → 返回 5 = n ✓ (所有元素 < 8)

7.6 为什么 `lower_bound` 不用 `<=` 和 `mid±1`？

标准二分需要 <= 和 mid±1 是因为目标是"精确匹配"——mid 被检查后如果不等就可以跳过。lower_bound 需要 < 和 hi=mid 是因为目标是"边界"——mid 可能就是答案，不能跳过。

标准二分:
  目标 [5] 查找 5 → lo=0, hi=0, 用 <= → 进入循环 ✓
  用 <  → 直接退出 → 漏判 ✗

lower_bound:
  目标 [5] 查找 5 → lo=0, hi=1, 用 < → 进入循环 ✓
  mid=0, arr[0]=5 >= 5 → hi=mid=0 → lo=hi=0 → 退出 → 返回 0 ✓
  此时 lo==hi 时区间 [lo, hi) 为空 → 答案已确定 → 不需要 <=

NOTE

lower_bound 的三个差异（hi=n, lo<hi, hi=mid）不是随意的——它们是一个精确的数学推导：改变区间语义从 [lo, hi] 到 [lo, hi)（左闭右开），所有边界条件同步调整。这是"循环不变式驱动设计"的经典型范。

8. 旋转有序数组的二分查找

8.1 什么是旋转有序数组？

旋转有序数组是一个有序数组在某一点"旋转"得到——把数组分为前后两段，交换位置。

原始有序数组: [0, 1, 2, 3, 4, 5, 6, 7]
旋转 4 个位置: [4, 5, 6, 7, 0, 1, 2, 3]
                └──┬──┘  └────┬────┘
               左半:有序    右半:有序

旋转点 = 最小值的位置 = 4

核心性质：旋转数组由两段各自有序的片段组成。如果能定位到"mid 落在左有序段还是右有序段"，就能推断 target 的可能区域。

8.2 策略一：两次二分（先找旋转点，再搜索）

Step 1: 找到最小值（旋转点）
  [4, 5, 6, 7, 0, 1, 2] → 最小值 0 在索引 4

Step 2: 根据 target 与边界的关系决定搜索哪一侧
  如果 target 在 [4, 7] → 在 [0..3] 中搜索
  如果 target 在 [0, 2] → 在 [4..6] 中搜索

search_rotated_two_pass.c

/* 找到旋转排序数组中的最小值索引（旋转点） */
int find_pivot(int arr[], int n) {
    int lo = 0, hi = n - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] > arr[hi])
            lo = mid + 1;    // 最小值在右半
        else
            hi = mid;        // 最小值在左半（含 mid）
    }
    return lo;
}

int search_rotated(int arr[], int n, int target) {
    int pivot = find_pivot(arr, n);
    int lo, hi;

    /* 决定在旋转点的左段还是右段中搜索 */
    if (target >= arr[pivot] && target <= arr[n-1]) {
        lo = pivot; hi = n - 1;     // 在右段
    } else {
        lo = 0; hi = pivot - 1;    // 在左段
        if (hi < 0) hi = 0;        // pivot=0 时左段为空
    }

    /* 标准二分查找 */
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

8.3 策略二：一次二分——边找有序侧边搜索

更优雅的方案：一次二分完成。每次判断 mid 落在左侧有序段还是右侧有序段，然后决定 target 在哪一侧。

search_rotated_one_pass.c

int search_rotated(int arr[], int n, int target) {
    int lo = 0, hi = n - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (arr[mid] == target)
            return mid;

        /* 判断 mid 落在左侧有序段还是右侧有序段 */
        if (arr[lo] <= arr[mid]) {
            /* 左侧 [lo..mid] 有序 */
            if (arr[lo] <= target && target < arr[mid])
                hi = mid - 1;    // target 在左侧有序段内
            else
                lo = mid + 1;    // target 在右侧（无序段）
        } else {
            /* 右侧 [mid..hi] 有序 */
            if (arr[mid] < target && target <= arr[hi])
                lo = mid + 1;    // target 在右侧有序段内
            else
                hi = mid - 1;    // target 在左侧（无序段）
        }
    }
    return -1;
}

8.4 逐步跟踪：查找 0 in [4, 5, 6, 7, 0, 1, 2]

arr = [4, 5, 6, 7, 0, 1, 2], target=0

轮1: lo=0, hi=6, mid=3, arr[3]=7
     arr[0]=4 <= arr[3]=7 → 左侧有序 [4,5,6,7]
     target=0, 不在 [4, 7] 区间内
     → lo = mid+1 = 4              [lo=4, hi=6]

轮2: lo=4, hi=6, mid=5, arr[5]=1
     arr[4]=0 <= arr[5]=1 → 左侧有序 [0,1]
     target=0, 在 [0, 1) 区间内
     → hi = mid-1 = 4              [lo=4, hi=4]

轮3: lo=4, hi=4, mid=4, arr[4]=0 == target → return 4 ✓

8.5 为什么旋转数组也能 O(log n)？

虽然数组整体不再有序，但每次二分后仍能排除一半搜索空间：

mid 落在左侧有序段 → arr[lo..mid] 全部有序
  → 如果 target 在有序段内 → 搜索左半
  → 如果不在 → target 必在右半（右半可能无序但一定包含 target）

mid 落在右侧有序段 → arr[mid..hi] 全部有序
  → 如果 target 在有序段内 → 搜索右半
  → 如果不在 → target 必在左半

→ 无论哪种情况，每次都能排除一半！

NOTE

旋转有序数组的二分是"思路迁移能力"的试金石——表面看数组不再有序，但利用"每次比较后仍能排除一半"的二分精髓，就能写出 O(log n) 的解法。这道题在面试中频繁出现，是标准二分查找之外最重要的变体。

参考解答

练习: binary_search 完整实现

solution_40_binary_search.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* 迭代二分查找：在大小为 n 的有序数组 arr 中查找 target
 * 找到返回索引，未找到返回 -1 */
int binary_search(int arr[], int n, int target)
{
    int lo = 0, hi = n - 1;

    while (lo <= hi) {
        /* mid = lo + (hi - lo) / 2 —— 防溢出，不用 (lo + hi) / 2 */
        int mid = lo + (hi - lo) / 2;

        if (arr[mid] == target)
            return mid;          /* 找到了！ */

        if (arr[mid] < target)
            lo = mid + 1;        /* target 在右侧，移动 lo（+1 防死循环） */
        else
            hi = mid - 1;        /* target 在左侧，移动 hi（-1 防死循环） */
    }

    return -1;                   /* 搜索空间为空，未找到 */
}

int main(void)
{
    char line[1024], tline[32];
    fgets(line, sizeof(line), stdin);
    fgets(tline, sizeof(tline), stdin);

    int arr[1024], n = 0, target;
    char *tok = strtok(line, " \n");
    while (tok) {
        arr[n++] = atoi(tok);
        tok = strtok(NULL, " \n");
    }
    sscanf(tline, "%d", &target);

    printf("%d\n", binary_search(arr, n, target));
    return 0;
}

核心决策说明：

mid = lo + (hi - lo) / 2 — 等价于 (lo + hi) / 2 但永不溢出。hi - lo 由循环不变式保证 ≤ n-1，远小于 INT_MAX。
while (lo <= hi) — 等号确保单元素搜索空间不被漏判。[5] 查找 5 时，lo==hi==0 仍需进入循环检查 arr[0]。
lo = mid + 1 / hi = mid - 1 — +1 和 -1 保证每次迭代搜索空间严格缩小，避免 lo=mid 在 lo+1==hi 时导致的死循环。
return -1 — 循环退出时 lo > hi，搜索空间为空，确认 target 不存在。

对照检查：mid 用的是 lo+(hi-lo)/2 吗？循环条件是 while (lo <= hi) 吗？lo 更新是 mid+1 不是 mid 吗？return -1 在循环外面吗？

课堂讨论

为什么二分查找要求数组有序？如果数组无序，二分查找的结果会怎样？能用二分查找在无序数组中"碰运气"吗？
在什么情况下 mid = (lo + hi) / 2 会溢出？为什么 mid = lo + (hi - lo) / 2 一定不会？用数学证明而非直觉。
如果把 while (lo <= hi) 改成 while (lo < hi)，有哪些测试用例会失败？请列举至少 3 个不同的场景。
标准二分查找和 lower_bound 在循环条件、hi 初值、hi 更新方式上都不相同——为什么？这些差异都源自什么样的语义差异？
旋转有序数组的二分查找为什么仍然是 O(log n)？如果 mid 落在无序的中间区域，算法怎么保证排除一半？
如果数组很大（n > 10 亿），二分查找的三个陷阱中哪个"一定"触发 bug、哪个"可能"触发、哪个"一定"不触发？为什么？

讨论答案

Q1: 为什么二分查找要求数组有序？

因为 arr[mid] < target ⇒ target 在右侧 这个推理仅当数组有序时成立。

无序数组反例：

arr = [5, 1, 9, 3, 7]，查找 3

mid = 2, arr[2] = 9 > 3
→ 如果按二分逻辑："target 在左侧" → 搜索 [0..1]
→ 但 3 实际在 arr[3]，被排除在外 → 找不到 ✗

能否"碰运气"，有时碰巧可以——比如 arr=[5, 3, 7]，查找 3：

mid = 1, arr[1] = 3 → 碰巧找到了 ✓

但这不是算法正确性的保证——结果是概率性的而非确定性的。算法定义为：对所有可能输入给出确定正确结果。二分查找在无序数组上不满足这一定义。

Q2: (lo+hi)/2 溢出的数学证明

证明 hi-lo 不溢出：

二分查找的循环不变式保证 0 ≤ lo ≤ hi ≤ n-1。因此：

hi - lo ≤ hi ≤ n - 1 ≤ INT_MAX

hi - lo 的最大值受限于 n，永远不会超过 INT_MAX（假设 n 本身不超过 INT_MAX——超过意味着数组无法用 32 位 int 索引，此时 int 本身就不适合作索引类型）。

证明 lo+hi 可能溢出：

取 lo = 1500000000, hi = 2000000000（两者均 < INT_MAX=2147483647）：

lo + hi = 3500000000 > 2147483647 = INT_MAX → 溢出

lo 和 hi 各自合法，但它们的和不合法——这正是加法的"进位"效应。

数学等价但工程不等价：

(lo + hi) / 2 = lo + (hi - lo) / 2    ← 数学恒等式

但在 C 语言中:
(lo + hi) / 2   → 先算 lo+hi，可能溢出
lo + (hi-lo)/2  → 先算 hi-lo，永不溢出，再算 +lo，安全

Q3: while(lo<hi) 在哪些场景失败？

场景 1：单元素数组，元素匹配

arr = [5], target = 5
lo=0, hi=0, 0<0=false → 不进入循环 → return -1 ✗

场景 2：单元素数组，元素不匹配

arr = [5], target = 3
lo=0, hi=0, 0<0=false → 不进入循环 → return -1 ✓

（巧合正确——因为正确答案就是 -1）

场景 3：target 在数组最后一个元素

arr = [1, 3, 5], target = 5
lo=0, hi=2 → mid=1, arr[1]=3<5 → lo=2
lo=2, hi=2 → 2<2=false → 不进入循环 → return -1 ✗

target 在 arr[2] 但算法未能检查它——因为当 lo 一步步收缩到 hi 的位置时，只剩下一个元素，但 lo < hi 不让进入循环。

结论：任何导致搜索空间最终收缩到单元素的情况，lo < hi 都会失败。唯一的例外是单元素恰好不匹配（此时正确答案是 -1，跳过循环也算对）。

Q4: lower_bound 和标准二分的语义差异分析

三处差异都源于区间语义的变化：

特征	标准二分	lower_bound
搜索语义	找等于 target 的任意位置	找第一个 ≥ target 的位置
区间表示	`[lo, hi]`（左闭右闭）	`[lo, hi)`（左闭右开）
可能答案范围	0 .. n-1	0 .. n（target 比所有元素大时答案=n）
hi 初值	n-1（最大有效索引）	n（允许返回 n）
循环条件	`lo ≤ hi`（区间非空）	`lo < hi`（区间长度 > 0）
hi 更新	hi = mid-1（mid 判断过了可跳过）	hi = mid（mid 可能是答案不能跳过）

为什么 hi=n？ — lower_bound 的语义允许返回值 n（表示所有元素都 < target）。区间 [0, n) 恰好覆盖 0 到 n-1 共 n 个可能位置。

为什么 lo < hi？ — 左闭右开区间 [lo, hi) 非空 ⇔ lo < hi。当 lo==hi 时区间为空，答案已收敛。

为什么 hi = mid？ — 当 arr[mid] >= target 时，mid 可能就是答案（第一个满足条件的位置），不能排除它。

所有差异都是从一个核心语义变化推导出来的——这就是"有语义的代码"，而不是凑出来的巧合。

Q5: 旋转数组二分为什么还是 O(log n)？

因为每次迭代仍能排除一半搜索空间。

虽然数组整体不有序，但有一个关键性质：mid 必定落在某一段有序子数组上。

以 arr = [4,5,6,7,0,1,2] 为例：

arr[lo]=4, arr[hi]=2

mid=3, arr[mid]=7:
  arr[lo]=4 ≤ arr[mid]=7 → 左侧 [4,5,6,7] 有序
  判断 target 是否处于 [4, 7] 内:
    - 是 → 搜索左半（有序段内标准二分）
    - 否 → 搜索右半（arr[mid+1..hi]）

mid=1, arr[mid]=5:
  arr[lo]=4 ≤ arr[mid]=5 → 仍然在左侧

mid=5, arr[mid]=1:
  arr[lo]=4 > arr[mid]=1 → 不满足 arr[lo]≤arr[mid]
  → 右侧 [1, 2] 有序

**每次都能排除一半**:
  情况 A: target 在有序段 → 搜索有序段（排除无序段）
  情况 B: target 不在有序段 → 搜索无序段（排除有序段）
  → 无论哪种，每次排除一半 → O(log n)

关键洞察：判断有序侧 + 判断 target 是否处于有序侧这个两步推理，保证了每次仍能"丢弃"一半数据。

Q6: 大数组（n > 10 亿）中三陷阱的触发概率

陷阱 1（mid 溢出）："一定"触发

当 n > 10^9 时，lo 和 hi 都有可能 > 5×10^8。经过几轮二分，lo+hi 极易超过 INT_MAX（约 2.14×10^9）。几乎任何大数组的二分都会在某个时刻触发溢出——这是确定性的 bug。

陷阱 2（循环条件缺等号）："可能"触发

当搜索空间收缩到 1 个元素且 target 恰好在这个位置上时触发。大数组增大了"最终搜索空间收缩到但元素"的概率，但具体触发与否取决于 target 是否在最后一个候选位置——这是数据依赖的。

陷阱 3（lo=mid 死循环）："可能"触发

当 lo+1==hi 且 target 落在 lo 侧时触发。在二分查找的最后阶段，搜索空间自然会收缩到 2 个元素——此时走 lo=mid 分支就死循环。触发条件是算法运行到最后两轮——几乎一定会遇到。

总结：

陷阱	大数组触发概率	原因
mid 溢出	100%（确定）	lo+hi 必然超过 INT_MAX
缺等号	数据依赖	取决于最后的搜索结果
lo=mid	~100%	最后阶段必然遇到 lo+1==hi

课后练习

递归实现二分查找，将迭代版本改写为递归版本。递归函数的参数需要什么？基准条件（base case）是什么？分析递归版和迭代版的优劣。

知识点提示：递归版代码更短（不需要显式管理 lo/hi 变量），但每次递归调用消耗栈空间，空间复杂度为 O(log n) 而非 O(1)。面试中迭代版更受青睐。

参考解答

binary_search_recursive.c

int binary_search_rec(int arr[], int lo, int hi, int target) {
    /* 基准条件：搜索空间为空 */
    if (lo > hi)
        return -1;

    int mid = lo + (hi - lo) / 2;

    if (arr[mid] == target)
        return mid;
    if (arr[mid] < target)
        return binary_search_rec(arr, mid + 1, hi, target);
    else
        return binary_search_rec(arr, lo, mid - 1, target);
}

/* 封装函数，保持与迭代版相同的接口 */
int binary_search(int arr[], int n, int target) {
    return binary_search_rec(arr, 0, n - 1, target);
}

迭代版 vs 递归版：

迭代：O(1) 空间，需要手动维护 lo/hi/mid
递归：O(log n) 栈空间，代码更简洁，基本案例更明确
面试：迭代版更受青睐（省空间 + 展示循环控制能力）

实现 upper_bound。找"第一个 > target"的位置（而非 ≥）。提示：只需修改 lower_bound 中的一个条件——arr[mid] <= target 而非 arr[mid] < target。

知识点提示：upper_bound 与 lower_bound 的差异只有一个字符——比较运算符从 < 变为 <=。理解这个差异：当 arr[mid]==target 时，upper_bound 应该排除 mid（因为 mid 位置的元素不满足"> target"），而 lower_bound 应该保留 mid（因为 mid 位置的元素满足"≥ target"）。

参考解答

upper_bound.c

/* 返回第一个 > target 的元素索引
 * 如果所有元素都 <= target，返回 n */
int upper_bound(int arr[], int n, int target) {
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] <= target)       // ← 唯一差异: < 改为 <=
            lo = mid + 1;             // arr[mid] 不满足 "> target"
        else
            hi = mid;                 // arr[mid] 满足，可能是答案
    }
    return lo;
}

arr = [1, 3, 3, 5, 7]
lower_bound(3) = 1  (第一个 ≥ 3)
upper_bound(3) = 3  (第一个 > 3 = arr[3]=5)

搜索旋转排序数组，实现本节所述的旋转有序数组二分查找（策略二：一次二分），并手动跟踪 [4,5,6,7,0,1,2] 中查找 0、6、3（不存在）三个目标值的完整过程。

知识点提示：核心是判断 arr[lo] <= arr[mid] 来区分 mid 落在左侧有序段还是右侧无序段，然后根据 target 是否处于有序段内决定搜索方向。

参考解答

search_in_rotated.c

#include <stdio.h>

int search_rotated(int arr[], int n, int target) {
    int lo = 0, hi = n - 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;
}

int main(void) {
    int arr[] = {4, 5, 6, 7, 0, 1, 2};
    int n = 7;

    printf("search 0: %d (expected 4)\n",
           search_rotated(arr, n, 0));
    printf("search 6: %d (expected 2)\n",
           search_rotated(arr, n, 6));
    printf("search 3: %d (expected -1)\n",
           search_rotated(arr, n, 3));
    return 0;
}

逐步跟踪：

查找 3 in [4,5,6,7,0,1,2]:
轮1: lo=0,hi=6,mid=3,arr[3]=7, 左侧有序[4..7], 3∉[4,7)→lo=4
轮2: lo=4,hi=6,mid=5,arr[5]=1, 左侧有序[0..2], 3∉[0,2)→hi=4
轮3: lo=4,hi=4,mid=4,arr[4]=0, 左侧有序[0], 3∉[0)→lo=5
退出: lo=5 > hi=4 → return -1 ✓

查找元素的第一个和最后一个位置。给定有序数组（可能含重复元素），返回 target 第一次出现和最后一次出现的索引。利用 lower_bound 和 upper_bound 实现——想想这两个函数的返回值如何映射到"第一个位置"和"最后一个位置"。

知识点提示：第一次出现 = lower_bound(target)，最后一次出现 = upper_bound(target) - 1。利用前面实现的 lower_bound → upper_bound，一行代码就能得到答案。

参考解答

search_range.c

#include <stdio.h>

int lower_bound(int arr[], int n, int target) {
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] < target)
            lo = mid + 1;
        else
            hi = mid;
    }
    return lo;
}

int upper_bound(int arr[], int n, int target) {
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] <= target)
            lo = mid + 1;
        else
            hi = mid;
    }
    return lo;
}

/* 返回 target 的出现范围 [first, last]
 * 如果不存在，first=-1, last=-1 */
void search_range(int arr[], int n, int target,
                  int *first, int *last) {
    int lo = lower_bound(arr, n, target);

    /* lo==n 或 arr[lo]!=target → target 不存在 */
    if (lo == n || arr[lo] != target) {
        *first = *last = -1;
        return;
    }

    *first = lo;
    *last = upper_bound(arr, n, target) - 1;
}

int main(void) {
    int arr[] = {1, 2, 2, 2, 3, 4, 5};
    int n = 7, first, last;

    search_range(arr, n, 2, &first, &last);
    printf("target 2: [%d, %d]\n", first, last); // [1, 3]

    search_range(arr, n, 6, &first, &last);
    printf("target 6: [%d, %d]\n", first, last); // [-1, -1]

    return 0;
}

arr = [1, 2, 2, 2, 3, 4, 5], target = 2
lower_bound(2) = 1        → arr[1]=2, 第一个出现位置 = 1
upper_bound(2) = 4        → arr[4]=3, 第一个 > 2 的位置 = 4
→ 范围 [1, 3] = [lower_bound, upper_bound-1]

三分查找（Ternary Search）的对比。将每次二分（比较后排除一半）改为三分——每次取两个中点（mid1 和 mid2）将数组分成三部分。实现后分析：三分查找的比较次数比二分多还是少？为什么实践中几乎不用？

知识点提示：三分查找在最坏情况下需要约 2×log₃n 次比较，而二分需要约 log₂n 次。虽然 log₃n < log₂n，但 2×log₃n > log₂n（因为 2/log₂3 ≈ 1.26 > 1）。这是"分得更细不一定更优"的经典反例。

参考解答

ternary_search.c

/* 三分查找——理解它为什么不如二分 */
int ternary_search(int arr[], int n, int target) {
    int lo = 0, hi = n - 1;

    while (lo <= hi) {
        int len = hi - lo;
        int mid1 = lo + len / 3;
        int mid2 = lo + 2 * len / 3;

        if (arr[mid1] == target) return mid1;
        if (arr[mid2] == target) return mid2;

        if (target < arr[mid1])
            hi = mid1 - 1;           // 在左侧 1/3
        else if (target > arr[mid2])
            lo = mid2 + 1;           // 在右侧 1/3
        else {
            lo = mid1 + 1;           // 在中间 1/3
            hi = mid2 - 1;
        }
    }
    return -1;
}

复杂度对比：

二分: 每轮 1 次比较，k 轮 → k 次比较
      n/2^k = 1 → k = log₂n

三分: 每轮 2 次比较（最坏），k 轮 → 2k 次比较
      n/3^k = 1 → k = log₃n

比较次数比: 2×log₃n / log₂n = 2/log₂3 ≈ 2/1.585 ≈ 1.26
→ 三分查找比二分查找多约 26% 的比较次数！

实践不用三分的原因：

比较次数更多（表面"分更细"，实际更慢）
逻辑更复杂（两个中点 vs 一个中点）
每轮两个分支判断增加分支预测失败概率

参考资料

《编程珠玑》(Programming Pearls) 第 4 章 — Jon Bentley 著。包含二分查找的经典论述和"90% 专家写错"的轶事。每一章都是一颗工程智慧珍珠
《算法导论》(Introduction to Algorithms) 二分查找章节 — 循环不变式的严格证明方法，是算法正确性验证的理论基础
Java Bug JDK-5045582 — Arrays.binarySearch 的 int 溢出 bug，从报告到修复贯穿 9 年，是"看似无害代码导致生产崩溃"的教科书级案例
Google Research Blog: TimSort Bug — 2015 年发现 Java/Android/Python 的 TimSort 中存在与二分查找相同的溢出 bug
LeetCode 704: Binary Search — 标准二分查找在线练习；LeetCode 33: Search in Rotated Sorted Array — 旋转有序数组二分；LeetCode 34: Find First and Last Position — lower_bound/upper_bound 实战

"The difference between a good programmer and a great one is the understanding of what happens at the boundaries." — 二分查找的边界条件（溢出、等号、±1）正是这句格言的最佳注脚。

Lesson 40: 二分查找 ​

练习任务 ​

核心知识点 ​

代码框架 ​

深度讲解 ​

1. O(log n) 对数时间与有序前提 ​

1.1 "二分"的含义 ​

1.2 线性 vs 二分力觉对比 ​

1.3 有序前提不能违背 ​

2. 陷阱 1：mid 计算溢出（最隐蔽的 bug） ​

2.1 错误写法与正确写法 ​

2.2 溢出过程逐帧还原（32 位 int，INT_MAX = 2147483647） ​

2.3 Java Arrays.binarySearch 的 JDK-5045582 Bug ​

3. 陷阱 2：循环条件 lo <= hi 的 <= 号 ​

3.1 两种写法的行为差异 ​

3.2 具体反例：单元素数组 ​

3.3 <= 的数学语义 ​

4. 陷阱 3：指针更新 lo = mid + 1 防止死循环 ​

4.1 错误写法导致的死循环 ​

4.2 死循环逐帧跟踪 ​

4.3 为什么 lo = mid 在 lo + 1 == hi 时会死循环？ ​

4.4 完整的三陷阱对照表 ​

5. 溢出具体数值演示——lo=1.5e9, hi=2e9 ​

5.1 数值轨迹完整推演 ​

5.2 为什么 (hi - lo) 永不溢出？ ​

6. Bentley《编程珠玑》轶事——"90% 的专家写不对" ​

6.1 原文轶事 ​

6.2 为什么 90% 的人都栽了？ ​

6.3 工程启示 ​

7. lower_bound 变体：找第一个 ≥ target 的位置 ​

7.1 标准二分 vs lower_bound ​

7.2 lower_bound 的三个核心差异 ​

7.3 lower_bound 完整实现 ​

7.4 lower_bound 循环不变式详解 ​

7.5 lower_bound 逐步跟踪 ​

7.6 为什么 lower_bound 不用 <= 和 mid±1？ ​

8. 旋转有序数组的二分查找 ​

8.1 什么是旋转有序数组？ ​

8.2 策略一：两次二分（先找旋转点，再搜索） ​

8.3 策略二：一次二分——边找有序侧边搜索 ​

8.4 逐步跟踪：查找 0 in [4, 5, 6, 7, 0, 1, 2] ​

8.5 为什么旋转数组也能 O(log n)？ ​

参考解答 ​

课堂讨论 ​

讨论答案 ​

课后练习 ​

参考资料 ​

Lesson 40: 二分查找

练习任务

核心知识点

代码框架

深度讲解

1. O(log n) 对数时间与有序前提

1.1 "二分"的含义

1.2 线性 vs 二分力觉对比

1.3 有序前提不能违背

2. 陷阱 1：mid 计算溢出（最隐蔽的 bug）

2.1 错误写法与正确写法

2.2 溢出过程逐帧还原（32 位 int，INT_MAX = 2147483647）

2.3 Java Arrays.binarySearch 的 JDK-5045582 Bug

3. 陷阱 2：循环条件 `lo <= hi` 的 `<=` 号

3.1 两种写法的行为差异

3.2 具体反例：单元素数组

3.3 `<=` 的数学语义

4. 陷阱 3：指针更新 `lo = mid + 1` 防止死循环

4.1 错误写法导致的死循环

4.2 死循环逐帧跟踪

4.3 为什么 `lo = mid` 在 `lo + 1 == hi` 时会死循环？

4.4 完整的三陷阱对照表

5. 溢出具体数值演示——lo=1.5e9, hi=2e9

5.1 数值轨迹完整推演

5.2 为什么 `(hi - lo)` 永不溢出？

6. Bentley《编程珠玑》轶事——"90% 的专家写不对"

6.1 原文轶事

6.2 为什么 90% 的人都栽了？

6.3 工程启示

7. lower_bound 变体：找第一个 ≥ target 的位置

7.1 标准二分 vs lower_bound

7.2 lower_bound 的三个核心差异

7.3 lower_bound 完整实现

7.4 lower_bound 循环不变式详解

7.5 lower_bound 逐步跟踪

7.6 为什么 `lower_bound` 不用 `<=` 和 `mid±1`？

8. 旋转有序数组的二分查找

8.1 什么是旋转有序数组？

8.2 策略一：两次二分（先找旋转点，再搜索）

8.3 策略二：一次二分——边找有序侧边搜索

8.4 逐步跟踪：查找 0 in [4, 5, 6, 7, 0, 1, 2]

8.5 为什么旋转数组也能 O(log n)？

参考解答

课堂讨论

讨论答案

课后练习

参考资料