二分查找

搜索算法

在有序数组中通过将目标值与数组中间值比较,每次将查找范围缩小一半。高效查找的经典算法,时间复杂度为 O(log n)。

时间复杂度:最佳 O(1) | 平均 O(log n) | 最差 O(log n)
空间复杂度:O(1)

应用场景/前提条件

  • 数组必须是有序的才能应用二分查找

算法讲解

二分查找

介绍

二分查找(Binary Search)是一种高效的查找算法,也叫折半查找。核心思想:对于一个有序的数据集合,每次查找都将查找范围缩小为原来的一半,直到找到目标值或确定目标值不存在。二分查找要求数据必须是有序的,经常应用于数组等支持随机访问的数据结构里。跟线性查找相比,二分查找的效率要高得多,特别是对于大规模数据集。

算法步骤

  1. 确定查找范围的左边界 left 和右边界 right
  2. 计算中间位置 mid = (left + right) / 2(注意整数溢出问题,更安全的做法是 mid = left + (right - left) / 2)
  3. 将中间位置的元素与目标值比较
    • 如果中间元素等于目标值,查找成功,返回中间元素的位置
    • 如果中间元素大于目标值,目标值可能在左半部分,将右边界调整为 mid - 1
    • 如果中间元素小于目标值,目标值可能在右半部分,将左边界调整为 mid + 1
  4. 重复步骤2-3,直到找到目标值或者左边界大于右边界(此时表示目标值不存在)

核心特性

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

...