二分查找

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

查找过程

假设，有序序列是升序的

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

代码实现

tim-chow的github

时间复杂度

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

参考文档

• 递归算法的时间复杂度分析