本文的核心内容来自LeetCode34.在排序数组中查找元素的第一个和最后一个位置中labuladong的题解二分查找算法详解，我是看了大佬的题解后，茅塞顿开，特来记录一下自己的学习心得。
算法思想
二分算法是一个入门级算法，在我刚接触Python编程时，就看到老师写了几行非常简单的代码，介绍了计算机分而治之的重要思想，顿时佩服的五体投地。
但等到自己上手写的时候，却总也写不对，也不是全不对，有时也会对，就是不能一遍过。思路很简单，细节是魔鬼。
二分搜索又叫二分查找，主要是用于顺序表结构的一种快速查找算法。首先列表为升序排列，从一个中间值将列表分为左和右两部分，用中间值与要查找值相比较，如果中间值大于查找值，查找值肯定不会在右表中，去左表查询。如果中间值小于查找值，那查找值肯定位于右表中。循环这个过程，不断的缩小查找空间，最终找到结果。
一、单数查找
我们先来看二分搜索最简单的一种场景，在升序列表中搜索一个数，如果存在，则返回索引，如果不存在，返回-1
代码如下：
def binarySearch(array: list, target: int) -> int:
left, right = 0, len(array) - 1 # 问题1：right 的值
while left <= right: # 问题2： < or <=
mid = (left + right) >> 1
if array[mid] == target:
return mid
elif array[mid] > target:
right = mid - 1 # 问题3：mid 还是mid -1
elif array[mid] < target:
left = mid + 1
return -1
问题一、区间问题
上面的代码中，right取值为len(array) - 1，这时right的值是数组最后一个元素的索引，这种情况称为闭区间，表示为[left,right]。
对应还有一种常见的取值方法为 right = len(array)，这种情况表示为[left, right)。
这是第一个区别，很关键。
问题二、while的退出条件是<=还是<
当取left <= right 时，最后一次满足条件是left = right = mid, 如果未满足array[mid] == target left = mid +1， 或者是right = mid - 1。 总之 left = right + 1，然后退出循环。
当取left < right 时，最后一次满足条件是left + 1 = right， 此时 mid = left，如果不满足条件，下一步是left = right，然后退出循环。
问题三、mid 的 加加减减
有时候left = mid + 1，right = mid - 1 有的时候left = mid,right = mid，这都是为什么呀？
这个地方的关键在于搜索区间是开还是闭。
当闭区间时[left, right]，我们的搜索空间是这样的： [left, mid-1], mid, [mid+1, right]，这样保证左中右是连续的，没有遗漏，也没有重叠。如果array[mid]大于target, 结果在左区间里，right = mid -1，反之，结果在右区间，left = mid + 1
当区间为开时，[left, right)，我们同样需要分割出来连续的搜索空间，结果是这样的： [left, mid), mid, [mid+1,right)，这时就很明了了，取左区间时right = mid, 取右区间时left = mid + 1
结合上面的三个小问题，我们用开区间写一个二分搜索，代码如下：
def binarySearch(array: list, target: int)-> int:
left, right = 0, len(array)
while left < right:
mid = (left + right) >> 1
if array[mid] == target:
return mid
elif array[mid] > target:
right = mid
elif array[mid] < target:
left = mid + 1
# 补丁，因为最后退出时的left没有检查，这里在检查一下。
if array[left] == target:
return left
return -1
边界查找
左侧边界
我们来看另一个例子，假如有序数组中存在重复，[1,2,3,3,3,4,5]这时我们查找数字3时，会返回索引为3。如果我们想得到重复数字的左侧边界，或右侧边界索引时，上面的算法就需要再改进一下。
代码如下：
def left_bound(array: list, target: int) -> int:
left, right = 0, len(array) - 1
while left <= right:
mid = (left + right) >> 1
if array[mid] == target: # 关键区别
right = mid - 1
elif array[mid] > target:
right = mid - 1
elif array[mid] < target:
left = mid + 1
return left
左侧边界还有另外一个解释，对于数组[2, 5, 7]，当我们用上面的代码查找 1 时 ，由于数组中不存在1，此时返回的结果为0，意思是数组中有0个元素比1小。当查找 8 时，返回 3，意思为有 3 个数字比 8 小。
这个算法和上面的二分搜索差别不大，最最关键区别就是array[mid] == target的处理。当我们找到一个目标值时，不要返回结果，而是将右边界修改为mid-1，继续在区间[left, mid-1]中查找左侧边界。
可能有同学有疑问，(其实有疑问的是我，手动Debug了好几遍才明白)，如果mid值就是左侧边界呢？我将区间设为[left, mid-1] 后不就找不到左边界了么？
这时，需要再看一下我们上面在闭区间中讨论的退出条件，当mid值是左边界，区间[left, mid-1] 里的值都比目标值小，left 会一直增大，直到left = right + 1 时退出循环，由于right = mid - 1，代入后，left = mid 所以退出时left还是仍是左侧边界。
能用闭区间完成，肯定也能用开区间完成，代码如下：
def open_interval_left_bound(array, target):
left, right = 0, len(array)
while left < right:
mid = (left + right) >> 1
if array[mid] == target:
right = mid
elif array[mid] > target:
right = mid
elif array[mid] < target:
left = mid + 1
return left
这种左闭右开的写法更常见一些。
右侧边界
右侧边界和左侧边界的区别主要是array[mid] == target时的判断，此时需要移动left = mid + 1，到右区间找右侧边界。
代码如下：
def right_bound(array: list, target: int) -> int:
left, right = 0, len(array) - 1
while left <= right:
mid = (left + right) >> 1
if array[mid] == target:
left = mid + 1
elif array[mid] > target:
right = mid - 1
elif array[mid] < target:
left = mid + 1
return right
左闭右开区间的右侧边界
代码如下：
def open_interval_right_bound(array: list, target: int) -> int:
left, right = 0, len(array)
while left < right:
mid = (left + right) >> 1
if array[mid] == target:
left = mid + 1
elif array[mid] > target:
right = mid
elif array[mid] < target:
left = mid + 1
return right - 1 # 关键点
我们对left的更新是 left = mid + 1，所以无论什么时候退出时，array[left] 都不会等于target。只有left - 1才可能是结果。
循环退出时时，left = right，所以 写成right - 1。
总结
至此，我们探索了二分搜索的细节问题，抄袭一下labuladong 大佬的总结：
基本二分查找
因为我们初始化 right = nums.length - 1
所以决定了我们的「搜索区间」是 [left, right]
所以决定了 while (left <= right)
同时也决定了 left = mid+1 和 right = mid-1
因为我们只需找到一个 target 的索引即可
所以当 nums[mid] == target 时可以立即返回
左侧边界二分查找
因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid + 1 和 right = mid
因为我们需找到 target 的最左侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧右侧边界以锁定左侧边界
右侧边界二分查找
因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid + 1 和 right = mid
因为我们需找到 target 的最右侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧左侧边界以锁定右侧边界
又因为收紧左侧边界时必须 left = mid + 1
所以最后无论返回 left 还是 right，必须减一