二分搜索

在有序数组中快速查找目标元素,每次将搜索范围缩小一半

可视化演示

步骤: 0 / 0时间复杂度: O(log n)空间复杂度: O(1)

二分搜索可视化

搜索目标: 0
左指针 (left): 0
中间位置 (mid): 0
右指针 (right): 0
未搜索
已淘汰
左指针
中间位置
右指针
找到目标

算法步骤

步骤 1: 设置左指针为数组起始位置,右指针为数组末尾位置

步骤 2: 计算中间位置 mid = (left + right) / 2

步骤 3: 比较中间元素与目标值

步骤 4: 如果相等,返回中间位置;如果目标值小于中间元素,右指针 = mid - 1;否则左指针 = mid + 1

步骤 5: 重复步骤2-4,直到左指针大于右指针

算法特性

优点:
  • • 时间复杂度低 O(log n)
  • • 空间复杂度低 O(1)
  • • 实现简单
  • • 效率高
缺点:
  • • 要求数组必须有序
  • • 不适合频繁插入/删除
  • • 不适合链表结构
  • • 缓存不友好

复杂度分析

最好情况
O(1)
平均情况
O(log n)
最坏情况
O(log n)
空间复杂度
O(1)

应用场景

适用场景:
  • • 有序数组查找
  • • 数据库索引查找
  • • 游戏中的数值查找
  • • 算法竞赛
不适用场景:
  • • 无序数组
  • • 链表结构
  • • 频繁修改的数据
  • • 小数据集

控制面板

0 / 0 步骤