前言
重要的事情说三遍，大厂面试必考，无论是前端还是移动还是后端，二分查找没有不考的！！！
二分查找思想
二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。
最简单的二分查找遍历实现
def bsearch(self, array, target):
low = 0
high = len(array) - 1
while low <= high:
mid = low + ((high-low)>>1)
if array[mid] == target:
return mid
elif array[mid] < target:
low = mid + 1
else:
high = mid - 1
return False
二分查找递归实现
def bsearch(self, array, target):
low = 0
high = len(array) - 1
return self.bsearchInternally(array, target, low, high)
def bsearchInternally(self, array, target, low, high):
if low > high:
return False
mid = low + ((high - low) >> 1)
if array[mid] == target:
return mid
elif array[mid] < target:
return self.bsearchInternally(array, target, mid + 1, high)
else:
return self.bsearchInternally(array, target, low, mid - 1)
上述代码有几个地方容易出错
循环退出条件
注意是 low<=high，而不是 lowmid 的取值
实际上，我们mid = low+((high-low)>>1)写成这样是为了将性能优化到极致，计算机处理位运算比除法是要快的。我们可能会想取中间位置不就是 mid=(low+high)/2 就可以了么？你一定会有这样的疑问，其实这种疑问开始我自己也会存在，经过思考以后发现，这种写法是有问题的。因为如果 low 和 high 比较大的话，两者之和就有可能会溢出。那么咱们可以改写为 mid = low+(high-low)/2 等价于 mid = low+((high-low)>>1)low 和 high 的更新
low=mid+1，high=mid-1。注意这里的 +1 和 -1，如果直接写成 low=mid 或者 high=mid，就可能会发生死循环。比如，当 high=3，low=3 时，如果 a[3]不等于 value，就会导致一直循环不退出。
二分查找应用场景
- 数组有序
- 数据量不宜太小
- 数据量也不能过大
贴一道实际算法题
在排序数组中查找元素的第一个和最后一个位置
class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
return [self.bsearch(nums, target, True), self.bsearch(nums, target, False)]
def bsearch(self, nums, target, firstOrLast):
low = 0
high = len(nums) - 1
while low <= high:
mid = low + ((high - low) >> 1)
if nums[mid] < target:
low = mid + 1
elif nums[mid] > target:
high = mid - 1
else:
if firstOrLast:
if mid == 0 or nums[mid - 1] != target:
return mid
else:
high = mid - 1
else:
if mid == len(nums) - 1 or nums[mid + 1] != target:
return mid
else:
low = mid + 1
return -1
