二分查找如何工作，它需要什么？

Question

二分查找如何工作，它需要什么？

Accepted Answer

**Binary search** 通过重复将搜索范围对半缩小，在**有序**数组中查找目标值。每次比较都会排除剩余元素的一半，时间复杂度为 **O(log n)**。 ## 原理查看中间元素。如果它等于目标值，完成。如果目标值较小，搜索左半部分；如果较大，搜索右半部分。重复此过程，直到找到目标或范围为空。 ## 例子 ```python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 # middle index if arr[mid] == target: return mid # found it elif arr[mid] < target: lo = mid + 1 # discard left half else: hi = mid - 1 # discard right half return -1 # not present binary_search([1, 3, 5, 7, 9], 7) # -> 3 ``` ## 追踪 ```text Search 7 in [1,3,5,7,9] lo=0 hi=4 mid=2 -> 5 < 7 => lo=3 lo=3 hi=4 mid=3 -> 7 == 7 => return 3 ``` ## 复杂度 - **Time:** O(log n)。**Space:** 迭代时为 O(1)。 ## 常见陷阱 **输入必须是有序的** —— 否则结果无意义。注意 `lo`/`hi` 中的off-by-one bugs，以及某些语言中的整数溢出问题（使用 `lo + (hi-lo)//2`）。 ## 为什么这很重要将搜索空间对半缩小，可以将百万元素的查找转化为约20次比较。其背后的分治模式在树、数据库和无数面试题中反复出现。理解它的唯一硬性要求——有序输入——能让你避免这个经典的隐蔽bug。