【算法笔记】二分查找

最近在做算法复健,鉴于我的blog域名难产,暂时寄居在何dalao这里。

什么是二分查找

二分查找又名折半查找。在一个有序数列中查找某个特定数/对象时,可以根据数的大小关系,每次将查找范围缩小到原来的一半,从而将查找所需的时间从O(n)缩小为O(logn).

举例:我需要在[1,4,5,7,12,15,19,27,33,41,49]这11个数中查找27.

如果正常按顺序检索,需要检索8次,当数据范围扩大到n时,时间复杂度为O(n).

如果采用二分查找,查找顺序如下:

  1. 记原数组为数组①,比较数组①中间的数(即15)与27的大小关系
  2. 由于15<27,检索数组修改为[19,27,33,41,49],记为数组②
  3. 比较数组②中间的数(即33)与27的大小关系
  4. 由于33>27,检索数组修改为[19,27],记为数组③
  5. 比较数组③中间的数(由于除法下取整,这里是19)与27的大小关系
  6. 由于19<27,检索数组修改为[27],发现27==27,记录此时27的索引(7),查找结束。

由于每次都会将检索范围缩小一半,所以时间复杂度为O(log_2n)

代码实现

这里代码出了点问题,下次再补(咕咕)

实战题目

二分查找可以用于解决“最大值最小”“最小值最大”这样的问题,其应用非常灵活。未完待续。

发表回复