二分查找

二分查找是针对有序结合，将区间分为两个，每次和区间的中位元素比较，以此循环直到找到元素或者区间的大小为 0。

实现

  • 循环退出条件：low <= high
  • mid 取值：mid = low + (high - low) >> 1
  • low 和 high 的更新：low = mid + 1; high = mid - 1

二分查找局限性

  • 依赖顺序表结构，即数组。需要元素的随机访问
  • 二分查找针对有序数组，原序列无序时需要先排序
  • 数据量太大不适合二分查找，二分查找需要顺序表结构，需要连续的地址空间，对内存要求较高。
  • 二分查找是和静态的数据序列，不适合动态变化的。

时间复杂度

二分查找采用不断的二分区间的做法，数据量为 n，经过 k 次二分查找有 $2^k = n$，则$k = log_2n$，时间复杂度是$O(logn)$