二分查找
介绍
二分查找(Binary Search)是一种高效的查找算法,也叫折半查找。核心思想:对于一个有序的数据集合,每次查找都将查找范围缩小为原来的一半,直到找到目标值或确定目标值不存在。二分查找要求数据必须是有序的,经常应用于数组等支持随机访问的数据结构里。跟线性查找相比,二分查找的效率要高得多,特别是对于大规模数据集。
算法步骤
- 确定查找范围的左边界 left 和右边界 right
- 计算中间位置 mid = (left + right) / 2(注意整数溢出问题,更安全的做法是 mid = left + (right - left) / 2)
- 将中间位置的元素与目标值比较
- 如果中间元素等于目标值,查找成功,返回中间元素的位置
- 如果中间元素大于目标值,目标值可能在左半部分,将右边界调整为 mid - 1
- 如果中间元素小于目标值,目标值可能在右半部分,将左边界调整为 mid + 1
- 重复步骤2-3,直到找到目标值或者左边界大于右边界(此时表示目标值不存在)

核心特性
- 要求有序:二分查找只适用于有序数据集合
- 时间复杂度:O(log n),在大规模数据集上非常高效
- 空间复杂度:迭代实现为O(1),递归实现为O(log n)(因为递归调用栈的深度)
- 随机访问:要求数据结构支持O(1)时间复杂度的随机访问(比如数组)
...