Overview
Binary Search 通过不断把 sorted array 对半缩小来查找 target。
Analogy
像查字典：先看中间，再决定往左还是往右。
Step-by-step
- 先设 low = 0，high = n - 1。
- 计算 mid = (low + high) // 2。
- 如果 arr[mid] == target，返回 mid。
- 如果 target 更小，high = mid - 1。
- 否则 low = mid + 1，循环条件是 low <= high。
Visual
[1 3 5 7 9] -> 看 5 -> 往右 -> 找到 7。
Common mistakes
- 更新 low/high 后忘记重新计算 mid。
- 循环写成 <，导致最后一个元素被跳过。
- mid = (low + high) 在某些语言可能溢出。
Practice questions
- 在 7 个元素的数组上分别演示存在和不存在的 target。
- 实现没找到时返回 insertion index 的版本。
- 用反例说明为什么必须是 sorted array。