二分查找

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

查找过程

设序列是升序的

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

Python 实现

tim-chow 的 Github

时间复杂度

二分查找算法中的基本操作是：比较元素，其频度是：

T(n) = T(n / 2) + 1 ===>
T(n) = T(n / 4) + 2 ===>
T(n) = T(n / 8) + 3 ===>
...
T(n) = T(n / 2m) + m

并且 T(1) = 1，所以当 m = log2n 时，T(n) = log2n。
因此，二分查找的时间复杂度是 O(logn)

延伸阅读

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