TheAlanWang

Notes

Binary Search

3 min read

Binary search = define what mid means, define valid(mid), then continue searching toward the side with a better boundary answer.

4 Steps

1. 明确在搜什么？

先确认：二分的是 index，还是 answer？

两大类：

  • 搜 index
    • 比如：（在有序数组里找某个数， 找第一个 >= target， 找最后一个 <= target）
  • 搜 answer
    • 比如：
      • Koko minimum eating speed
      • minimum capacity
      • maximum minimum distance
      • split array largest sum

这类题不是在数组里找位置，
而是在一个答案区间里猜一个值 mid，然后验证它行不行。

2. mid 代表什么？

不要一上来写：mid = (l + r) // 2,

先确认：

这个 mid 在这题里是什么意思？

例如：

  • Koko 里，mid = 吃香蕉速度
  • Capacity to ship packages 里，mid = 船的容量
  • rightmost_leq 里，mid = 数组下标

3. valid(mid) 是什么？

这个 mid 合不合法？

你要先定义出一个判断函数：valid(mid)

  • 例如：
    • Koko: valid(spd) = total_hours <= h
    • rightmost_leq: valid(m) = a[m] <= target
    • First bad version: valid(m) = isBadVersion(m)

4. valid 后往哪边继续找？

核心: 不要背：valid 后 move left / move right，而要想：

找到 valid 的 mid 后，往“可能存在更优答案”的那边继续搜。

Example 1：找最小 valid

  • 比如 Koko：mid 可行 → 想更小 → 继续搜左半边 → right = mid - 1
if valid(mid):  
    ans = mid  
    right = mid - 1  
else:  
    left = mid + 1

Example 2：找最大 / 最右 valid

  • 比如 rightmost_leq：mid 满足条件 → 想更大 → move left pointer
if valid(mid):  
    ans = mid  
    left = mid + 1  
else:  
    right = mid - 1

图像化理解

Binary search 常常是在找这种边界：

Example 1：找最小 valid

FFFFFTTTTT  
     ^

要找第一个 T, 所以：

  • mid 是 T，先记下来
  • 但还想往左找更早的 T
  • 所以 right = mid - 1

Example 2：找最大 / 最右 valid

TTTTTFFFFF  
    ^

你要找最后一个 T
所以：

  • mid 是 T，先记下来
  • 但还想往右找更晚的 T
  • 所以 left = mid + 1

Graph View