Binary Search

二分查找在有序数组中每次折半比较，O(log n) 定位目标，是高效搜索的基础算法。

用途

在有序数据中高效定位元素，将对数复杂度应用于搜索。

机制

维护 [lo, hi] 区间，mid=(lo+hi)/2，比较 mid 与目标：相等返回，小于搜右半，大于搜左半。每次区间减半，O(log n)。需有序前提。变体：下界、上界、插入位置。

用例

有序数组查找
数据库 B+树索引
版本控制 bisect
求函数零点（二分法）

示例

输入
```
Search 5 in [1,3,5,7,9]
```
输出
```
Index 2
```
2 comparisons

常见错误

lo+hi integer overflow: Use lo+(hi-lo)/2

相关词条

Sorting Algorithm

排序算法将元素按序排列，常见有快速排序、归并排序、堆排序等，复杂度从 O(n log n) 到 O(n²)。

Big O 记法描述函数渐近上界，用于分析算法时间/空间复杂度，忽略常数与低阶项。

哈希表用哈希函数将键映射到桶数组，平均 O(1) 查找/插入/删除，是最常用的数据结构之一。

参考链接