二分查找 Binary Search Algorithm

二分查找的前提

1. 目标函数单调性（单调递增或递减，支队有序数组有效）
2. 存在上下界（bounded）
3. 能够通过索引访问（index accessible）

定义

也称折半搜索算法(half-interval search algorithm)、对数搜索算法(logarithmic search algorithm) 是一种有序数组中查找特定元素的搜索算法。

• 搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束。
• 如果某一特定元素大于或小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果某一步骤数组为空，则代表找不到，这种搜索算法每一次比较都是搜索范围缩小一半。

复杂度

• 时间复杂度：O(log n)
• 空间复杂度：O(1)

代码模版

left, right = 0, len(array) - 1 

while left <= right: 

  mid = (left + right) / 2 

  if array[mid] == target: 

    # find the target!! 

    break or return result 

  elif array[mid] < target: 

    left = mid + 1 

  else: 

    right = mid - 1