二分搜索，你还在用三个模版？一个就够了！
One Template for All Binary Search Problems
背景
首先，面对二分搜索，我们往往会碰到以下疑问：
-
left和right初始值？ -
循环条件是
left < right还是left <= right？ -
如何更新
left和right？left = mid，left = mid + 1，right = mid,right = mid — 1? -
结束时要选
left还是right？
另外，二分搜索有多个场景，
-
标准的二分查找
-
二分查找左边界
-
二分查找右边界
-
二分查找极值点
对于上述多个场景，网上也有相关的模板，但是很多都是使用多个模版来针对性解决不同场景的应用问题。
但是，其实只要一个模板就够了！可能有很多大佬在用，本文只作总结，并提炼出统一的方法来应对上述不同场景。
模版
def binary_search(array) -> int:
def condition(value) -> bool:
pass
left, right = search_space_
while left < right:
mid = left + (right - left) // 2
if condition(mid):
right = mid
else:
left = mid + 1
return left
几个注意点：
left和right是解空间的闭区间- 循环结束时，
**left**是满足**condition**的最小值 right的取值是有讲究的，下面会提到
应用
下面使用这一个模板来解决几个常见场景的问题。
寻找插入点
https://leetcode.cn/problems/search-insert-position
def searchInsert(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] >= target:
right = mid
else:
left = mid + 1
return left
几个注意点：
right = len(nums)：上面提到，left和right是解空间的闭区间；当 target 比所有值大时，必定是落在索引len(nums)上面。- 返回值
left是满足nums[mid] ≥ target的最小值，即要么等于要么大于
寻找左边界
# ====== left bound ===========
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] >= target:
right = mid
else:
left = mid + 1
if nums[left] != target:
return [-1, -1]
几个注意点：
- 返回值
left是满足nums[mid] ≥ target的最小值：即要么找到等于 target 的最小值，返回该左边界；要么找到大于 target 的最小值，返回 -1
寻找右边界
# ====== right bound ===========
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] > target:
right = mid
else:
left = mid + 1
if left == 0:
if nums[left] != target:
return -1
else:
return 0
if nums[left - 1] != target:
return [-1, -1]
几个注意点：
right = len(nums)：上面提到，left和right是解空间的闭区间；当 target 比所有值大时，必定是落在索引len(nums)上面。- 返回值
left是满足nums[mid] > target的最小值，因此解是left-1 if left == 0的判断：因为返回值是left-1，因此多了这么一步判断
寻找极值点
def findPeakElement(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[mid + 1]:
right = mid
else:
left = mid + 1
return left
注意点：返回值left是满足nums[mid] > nums[mid+1]的最小值
综合应用题
- 寻找分割点：
left是满足条件的最小值，因此我们找的是右半段的左边界，并且由此计算左半段的右边界，重新赋值给left； - 得到两段为
[start, left]和[left + 1, end]； - 判断
target所在的段，并进行普通二分搜索
def search(self, nums: List[int], target: int) -> bool:
n = len(nums)
start, end = 0, n - 1
while start < end and nums[start] == nums[end]:
end -= 1
# 1. 寻找分割点（小于 nums[start] 的第一个值）
left, right = start, end
while left < right:
mid = left + (right - left) // 2
if nums[mid] < nums[start]:
right = mid
else:
left = mid + 1
# 1.1. 如果存在分割点，则将 left 作为左半段的右边界
if nums[start] > nums[left]:
left = left - 1
if nums[start] <= target:
left, right = start, left
else:
left, right = left + 1, end
# 2. 普通二分搜索
while left < right:
mid = left + (right - left) // 2
if nums[mid] >= target:
right = mid
else:
left = mid + 1
# 2.2. 小插曲，通过测试用例排除
# 出现的原因是上面进行了 left, right = left + 1, end 的赋值
# 导致 left > right，因此需要作此判断
if left > end:
return False
return True if nums[left] == target else False
结论
记住下面两句话，重新刷一下二分搜索，你会发现如鱼得水。
left和right是解空间的闭区间- 循环结束时，
**left**是满足**condition**的最小值
