003 · Binary Search
My First Thoughts
题目输入是一个升序数组 nums 和一个目标值 target，输出是 target 的 index；如果找不到，就返回 -1。
最直接的做法是从头到尾遍历。遇到等于 target 的元素，就返回当前 index；如果走完整个数组都没找到，就返回 -1。
def search(nums: list[int], target: int) -> int:
for i, num in enumerate(nums):
if num == target:
return i
return -1这个写法是正确的，但它没有真正利用“数组已经升序”这个条件。
既然数组是升序的，如果遍历到某个数已经大于 target，后面的数只会更大，就可以提前停止：
def search(nums: list[int], target: int) -> int:
for i, num in enumerate(nums):
if num == target:
return i
if num > target:
return -1
return -1这比普通遍历更聪明一些，但最坏情况下仍然要看完整个数组。例如 target 在最后一个位置，或者比所有元素都大，时间复杂度还是 \(O(n)\)。
Why That Is Not Enough
题目明确要求 \(O(\log n)\)，所以线性扫描不够。
升序数组真正有价值的地方是：每次看中间元素时，都可以直接排除一半范围。
- 如果
nums[mid] == target，直接返回mid - 如果
nums[mid] > target，说明答案只可能在左半边 - 如果
nums[mid] < target，说明答案只可能在右半边
一开始容易想到把数组切成左半边或右半边继续找：
nums = nums[:mid]
nums = nums[mid + 1:]但这样会带来两个问题。
第一，切片会创建新数组，产生额外开销。第二，更重要的是，切片之后 index 会从 0 重新开始，而题目要返回的是原数组里的 index。
所以不应该真的裁剪数组。我们只需要维护当前还可能包含答案的左右边界。
Final Idea
用两个指针 left 和 right 表示当前搜索范围。
每一轮取中点：
mid = (left + right) // 2// 是整除，结果自动向下取整。数组长度是偶数时，中点会落在左半边的最后一个位置，不需要任何特殊处理。
然后比较 nums[mid] 和 target：
- 相等，返回
mid - 中间值太大，把右边界移到
mid - 1 - 中间值太小，把左边界移到
mid + 1
当 left > right 时，说明搜索范围已经为空，返回 -1。
Why It Works
因为 nums 是升序数组，所以中间元素可以把当前范围分成两部分。
如果 target 小于 nums[mid]，它不可能出现在 mid 右侧；如果 target 大于 nums[mid]，它不可能出现在 mid 左侧。
每次比较之后，搜索范围都会缩小一半，但 left、right 和 mid 始终是原数组的 index，因此不需要额外保存偏移量。
Code
def search(nums: list[int], target: int) -> int:
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1Complexity
| Time | \(O(\log n)\) — 每次排除一半搜索范围 |
| Space | \(O(1)\) — 只维护左右边界和中点 |
Takeaway
在升序数组中查找目标值时，不要真的切分数组。维护
left和right两个边界，就能在保留原始 index 的同时，每次排除一半搜索范围。二分查找的关键不是“取中位数”，而是“用中点比较结果缩小答案可能存在的区间”。
← Quiz