二分查找(上)

  • A+
所属分类:算法与数据结构

二分查找(上)

复杂度

二分查找的时间复杂度是O(logn)。2^34之多的数据,最多比较34次就出来结果了。有时比O(1)还快,因为O(1000)也是O(1)。空间复杂度O(1)

代码

局限

  1. 数据结构要为数组,因为用到随机访问,不能用链表。
  2. 数据要有序,无序的可以用O(nlogn)复杂度的排序算法进行排序。多次查找可以摊平排序的复杂度。如果频繁插入、删除,则需要重新排序,采用二分法则不划算。
  3. 数据量太大也不适合。因为数组需要一大块连续的存储空间。

 

对于“值等于给定值”的问题,更常用散列表和二叉树。但二分查找更适合用在“近似查找”问题上。二分查找(下):二分查找变体中将介绍。

LTXU

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: