二分查找法简介
二分查找法属于分治算法的一种，其实在计算机发明之前就已有应用，在计算机科学中，更是大显光彩，几乎所有与数据索引有关的算法中都会直接或间接的采用二分查找法。二分思想同时也是计算机思维中最最重要的一个点。
标准的二分查找
二分查找的列表对象一定是有序的数组，首先必须是经过排序的，否则无法确定目标数据的大体方位，其次数据结构必须支持时间复杂度O(1)的下标访问，比如数组，若换成链表也不能用二分查找。
二分查找的思路是这样的：因为数组经过了排序，所以我先拿数组中间的一个元素来比较，如果命中目标数据则算法结束，如果小于目标数据，则说明目标数据在右半部分，如果大于目标数据，则说明在左半部分。这样一个流程之后，即使没有命中，咱们也很容易抛掉1/2的数据。按照这样的效率，即使运气再差，对于一个长度为N的数组来说，经过logN次抛弃之后最终会剩下一个数，要么命中，要么不存在。
下面我们看看一个标准的二分查找算法实现：
def binary_search(arr, left, right, hkey):
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == hkey:
return mid
elif arr[mid] < hkey:
left = mid + 1
elif arr[mid] > hkey:
right = mid - 1
return -1
算法很简单，命中目标则返回数组下标，否则返回-1 。
上面有一个小优化是 mid的算法，通常是(left+right)//2，这里为了避免left+right的结果溢出，因此用了left + (right – left) // 2 来提升left和right的计算范围。
二分查找法四种变形
- 查找第一个大于等于给定值得元素
- 查找最后一个小于等于给定值的元素
- 查找第一个值等于给定值的元素
- 查找最后一个值等于给定值的元素
我们先看前面两种。其实非常简单，根本无须判断边界条件。
上面的标准算法在查找失败的时候返回-1，但是我们在应用中常常会遇到这样的情况：虽然这个数没有找到，但是我要拿小于他的最大值，或者大于他的最小值。
我们先看如何取小于目标的最大值。
def binary_search(arr, left, right, hkey):
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == hkey:
return mid
elif arr[mid] < hkey:
left = mid + 1
elif arr[mid] > hkey:
right = mid - 1
return right
我曾经在边界条件的处理上煞费苦心过一番，又加了许多额外的判断，其实是真传一行码。上面算法在while循环结束后，left和right位置互换，却正好是一个大于目标值，一个小于目标值。所以要返回小于目标的最大值就返回right，返回大于目标的最小值，就返回left。
那么对于后面两种也可以借鉴上面的思路了。等于目标的第一个值就是
def binary_search(arr, left, right, hkey):
while left <= right:
mid = left + (right - left) // 2
if arr[mid] < hkey:
left = mid + 1
elif arr[mid] >= hkey:
right = mid - 1
return right