二分查找算法

二分查找

二分查找也叫折半查找。它用于从一个有序序列中,查找目标元素所处的位置。


查找过程

假设,有序序列是升序的

  • 将目标元素 与 序列 中间位置的元素 进行比较
    • 如果相等,则查找结束
    • 如果小于,则从左侧的子序列中,以相同的方式继续进行查找
    • 如果大于,则从右侧的子序列中,以相同的方式继续进行查找
    • 一直到,子序列为空,如果仍然没有查找到,则返回-1

代码实现

tim-chow的github


时间复杂度

在最坏的情况下,基本操作(比较目标元素 和 子序列中间位置的元素)的重复执行的次数是:
T(n) = T(n/2) + 1 --->
T(n) = (T(n/4) + 1) + 1 --->
...
T(n) = T(n/k) + log2k 并且 T(1) = 1,所以:
T(n) = log2n


参考文档

感谢浏览tim chow的作品!

如果您喜欢,可以分享到: 更多

如果您有任何疑问或想要与tim chow进行交流

可点此给tim chow发信

如有问题,也可在下面留言: