二分查找问题的通用代码模板
二分查找的思想很简单，但是在代码的书写过程中存在着很多的陷阱，尤其是二分查找有着很多的变种问题，例如：
查找第一个与target值相等的元素，若不存在则返回None
查找最后一个与target值相等的元素，若不存在则返回None
查找第一个大于target值的元素，若不存在则返回None
查找第一个大于等于target值的元素，若不存在则返回None
查找最后一个小于target值的元素，若不存在则返回None
查找最后一个小于等于target值的元素，若不存在则返回None
一般常见的代码模板如下：
def BinarySearch(nums:list,target:int)-> int:
"""
二分查找常见代码
Args:
nums (list): 有序数组
target (int): 目标值
Returns:
_type_: 目标值在数组中的下标
"""
right = len(nums)-1
left = 0
while left <= right:
mid = left + (right-left)//2 # 计算中间元素的index
if target == nums[mid]:
return mid # 找到即退出
elif target < nums[mid]:
right = mid - 1
else:
left = mid + 1
return None # 未找到则返回空值
在该代码中，我们将左边界设为第一个元素，右边界设为最后一个元素，计算中间元素的index，在寻找到一个与target值相等的中间元素时就退出。
通过观察上面的代码，我们可以发现一个问题，每次在更新left或者riget的值时，需要对mid进行加一或者减一的操作，而在一些寻找边界的问题中，这里的mid+1，mid-1或者直接用mid的判断就会很绕，这导致代码书写很容易出错。
为了解决这个问题，最好的办法就是将不同的问题都归到统一套代码模板内，在面对不同的变种问题时，只需要修改很少的关键步骤即可。因此，这里将上面的代码修改为如下的形式：
def BinarySearch(nums:list,target:int)-> int:
"""
二分查找通用代码模板
该问题中查找到了第一个等于target的元素的下标,有序序列升序排列
Args:
nums (list): 有序数组
target (int): 目标值
Returns:
_type_: 目标值在数组中的下标
"""
blue = -1 # !关键点1：修改初始条件的值,其中blue代表左半侧，red代表右半侧
red = len(nums)
while blue + 1 != red:
mid = blue + (red-blue)//2 #! 计算中间元素的index
if nums[mid] < target: #! 判断中间元素属于蓝色区还是红色区
# * 不同的问题变种需要修改的位置一
blue = mid
else:
red = mid
if red < len(nums) and nums[red] == target: #! 判断边界值
return red
#* 不同的问题变种需要修改的位置二
else:
return None # 未找到则返回空值
代码思路解析
为了示例，我们将有序序列nums(默认为升序)设为 [1,2,3,4,5,6,6,6,7,8]，同时，将target值设为6，我们将要查找出第一个等于6的元素的下标。
为了更好的理解二分查找问题，我们将序列中的元素进行颜色标记，分别记为红色和蓝色。在这个问题中，很容易可以得出，所有小于6的元素为蓝色，大于等于6的元素为红色，如下所示：
[1,2,3,4,5,6,6,6,7,8]
可见，我们要找的实际上就是第一个颜色为红色，而且值等于6的元素的下标。
因此，我们就把一个查找问题转化成了对数组进行染色的问题。
设置两个变量blue和red，使得blue始终指向蓝色区域的最后一个元素，red始终指向红色区域的第一个元素，由于问题开始时，我们并不知道序列的颜色分布，因此blue的初始值在第一个元素的左侧，即为blue = -1，红色的初始值在最后一个元素的右侧，即为red = len(nums)，这个具体问题里，red初始值为10。
接下来，我们就进入循环来对整个数组划分颜色，首先考虑我们何时退出循环？
很容易就想出，只要我们把整个数组的所有数据都涂上了颜色，就该退出循环了。此时，蓝色区间和红色区间中不再被未染色元素间隔开，也就是说blue+1 == red。因此，对应在while循环里，我们的循环退出条件永远是blue+1 != red。
让我们来考虑一下特殊情况，如果数组nums为空，那么blue初始值为-1，red初始值为0，这个时候blue加1正好等于red，我们不会进入循环，直接进入用于返回结果的判断语句。
接下来，计算第一次的中间元素的index，即为mid = blue + (red-blue)//2，这个具体问题里，第一次的mid值为-1+(10-(-1))//2 = 4。然后根据我们最开始对元素进行染色的标准：所有小于6的元素为蓝色，大于等于6的元素为红色，让我们来对mid应该染什么色来进行判断，由于nums[4]的值为5，小于6，所以这里mid应该染蓝色，也就是blue = mid。这样我们就执行完了第一次的循环操作，下面类似的进入后续的循环，直到把所有的数据都染上了色就退出循环。
在所有数据都染色之后，我们就可以判断返回值了，由于我们要找的是第一个颜色为红色，而且值等于6的元素的下标，所以循环结束后，我们直接判断red对应的元素是否存在，而且值是否等于6即可。
根据上述的分析，我们可以发现，当需要查找满足不同条件的值时，我们只需要找到元素的染色标准(也就是循环内的if判断语句的判断条件)，以及返回值的判断标准即可(也就是返回值判断语句的判断标准)即可，不需要去煞费脑筋地思考到底是left和right的值是mid+1还是mid-1还是直接用mid(或者是不思考，排列组合都试一遍看哪个能通 )。
利用标准模板解决二分查找系列问题
好了，到这里我们的二分查找问题的解法模板已经有了，那就是首先找到数组的染色标准，然后找到我们需要的返回值的判断标准，现在就该回头去看看文章一开始提出的6个问题了：
查找第一个与target值相等的元素，若不存在则返回None
查找最后一个与target值相等的元素，若不存在则返回None
查找第一个大于target值的元素，若不存在则返回None
查找第一个大于等于target值的元素，若不存在则返回None
查找最后一个小于target值的元素，若不存在则返回None
查找最后一个小于等于target值的元素，若不存在则返回None
利用刚才的思路，我们可以得出这6个问题的染色标准和返回值判断标准分别是:
所有小于target值的元素是蓝色，大于等于target值的元素是红色；
如果red对应的元素存在，而且值等于target，就返回red，否则返回空值。所有小于等于target值的元素是蓝色，大于target值的元素是红色；
如果blue对应的元素存在，而且值等于target，就返回blue，否则返回空值。所有小于等于target值的元素是蓝色，大于target值的元素是红色；
如果red对应的元素存在，就返回red，否则返回空值。所有小于target值的元素是蓝色，大于等于target值的元素是红色；
如果red对应的元素存在，就返回red，否则返回空值。所有小于target值的元素是蓝色，大于等于target值的元素是红色；
如果blue对应的元素存在，就返回blue，否则返回空值。所有小于等于target值的元素是蓝色，大于target值的元素是红色；
如果blue对应的元素存在，就返回blue，否则返回空值。
六个问题对应的代码分别是：
def BinarySearch(nums:list,target:int)-> int:
"""
查找第一个与target值相等的元素,若不存在则返回None
Args:
nums (list): 有序数组
target (int): 目标值
Returns:
_type_: 目标值在数组中的下标
"""
blue = -1 # !关键点1：修改初始条件的值,其中blue代表左半侧，red代表右半侧
red = len(nums)
while blue + 1 != red:
mid = blue + (red-blue)//2 #! 计算中间元素的index
if nums[mid] < target: #! 判断中间元素属于蓝色区还是红色区
# * 不同的问题变种需要修改的位置一
blue = mid
else:
red = mid
if red<len(nums) and nums[red] == target: #! 判断边界值
return red
#* 不同的问题变种需要修改的位置二
else:
return None # 未找到则返回空值
def BinarySearch(nums:list,target:int)-> int:
"""
查找最后一个与target值相等的元素,若不存在则返回None
Args:
nums (list): 有序数组
target (int): 目标值
Returns:
_type_: 目标值在数组中的下标
"""
blue = -1 # !关键点1：修改初始条件的值,其中blue代表左半侧，red代表右半侧
red = len(nums)
while blue + 1 != red:
mid = blue + (red-blue)//2 #! 计算中间元素的index
if nums[mid] <= target: #! 判断中间元素属于蓝色区还是红色区
# * 不同的问题变种需要修改的位置一
blue = mid
else:
red = mid
if blue >= 0 and nums[blue] == target: #! 判断边界值
return blue
#* 不同的问题变种需要修改的位置二
else:
return None # 未找到则返回空值
def BinarySearch(nums:list,target:int)-> int:
"""
查找第一个大于target值的元素,若不存在则返回None
Args:
nums (list): 有序数组
target (int): 目标值
Returns:
_type_: 下标
"""
blue = -1 # !关键点1：修改初始条件的值,其中blue代表左半侧，red代表右半侧
red = len(nums)
while blue + 1 != red:
mid = blue + (red-blue)//2 #! 计算中间元素的index
if nums[mid] <= target: #! 判断中间元素属于蓝色区还是红色区
# * 不同的问题变种需要修改的位置一
blue = mid
else:
red = mid
if red < len(nums): #! 判断边界值
return red
#* 不同的问题变种需要修改的位置二
else:
return None # 未找到则返回空值
def BinarySearch(nums:list,target:int)-> int:
"""
查找第一个大于等于target值的元素,若不存在则返回None
Args:
nums (list): 有序数组
target (int): 目标值
Returns:
_type_: 下标
"""
blue = -1 # !关键点1：修改初始条件的值,其中blue代表左半侧，red代表右半侧
red = len(nums)
while blue + 1 != red:
mid = blue + (red-blue)//2 #! 计算中间元素的index
if nums[mid] < target: #! 判断中间元素属于蓝色区还是红色区
# * 不同的问题变种需要修改的位置一
blue = mid
else:
red = mid
if red < len(nums): #! 判断边界值
return red
#* 不同的问题变种需要修改的位置二
else:
return None # 未找到则返回空值
BinarySearch(nums:list,target:int)-> int:
"""
查找最后一个小于target值的元素,若不存在则返回None
Args:
nums (list): 有序数组
target (int): 目标值
Returns:
_type_: 下标
"""
blue = -1 # !关键点1：修改初始条件的值,其中blue代表左半侧，red代表右半侧
red = len(nums)
while blue + 1 != red:
mid = blue + (red-blue)//2 #! 计算中间元素的index
if nums[mid] < target: #! 判断中间元素属于蓝色区还是红色区
# * 不同的问题变种需要修改的位置一
blue = mid
else:
red = mid
if blue >= 0: #! 判断边界值
return blue
#* 不同的问题变种需要修改的位置二
else:
return None # 未找到则返回空值
def BinarySearch(nums:list,target:int)-> int:
"""
查找最后一个小于等于target值的元素,若不存在则返回None
Args:
nums (list): 有序数组
target (int): 目标值
Returns:
_type_: 下标
"""
blue = -1 # !关键点1：修改初始条件的值,其中blue代表左半侧，red代表右半侧
red = len(nums)
while blue + 1 != red:
mid = blue + (red-blue)//2 #! 计算中间元素的index
if nums[mid] <= target: #! 判断中间元素属于蓝色区还是红色区
# * 不同的问题变种需要修改的位置一
blue = mid
else:
red = mid
if blue >= 0: #! 判断边界值
return blue
#* 不同的问题变种需要修改的位置二
else:
return None # 未找到则返回空值