二分法：根据特定值查找模板

模板代码


# 查找特定值的
def binarySearch(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# 查找左边界的
def binarySearch(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
						# 因为是查找左边界，所以遇到目标时，不能直接返回，
						# 应该通过修改 right 来缩小搜索范围
            right = mid - 1   
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    # End Condition: left > right
		if left >= len(nums):
				return -1
    return left if nums[left] == target else -1

# 查找左边界
def binarySearch(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
						# 因为是查找左边界，所以遇到目标时，不能直接返回，
						# 应该通过修改 right 来缩小搜索范围
            left = mid + 1   
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    # End Condition: left > right
		if right < 0:
				return -1
    return right if nums[right] == target else -1

上述三个模板第一个最好理解，找打target直接返回即可，若最后遍历完nums依旧没有找到那么返回-1。第二个模板寻找左边界，所以当mid是target时，通过right = mid - 1来缩小搜索范围。在python中，因为如果left,right只相差1的话，mid是等于left的，所以left一定是最后指向target的做左边，即左边界。比如最后left,right都指向同一个target（该target为最左边target）,此时由代码知，right 会再等于mid-1，所以最后是left指向最左边的target

但是当nums中不存在目标值时，要考虑以下三种情况：

target大于所有nums

此时， left会越界 left = len(nums)

target 小于所有nums

此时right会越界， right = -1

target在nums中某两个值中间

不会越界，但是left，right都不是指向target

但是，此时只关注left即可，通过判断left即可知道有无目标值

第三个模板寻找右边界，所以当mid是target时，通过left = mid + 1 来缩小搜索范围。最后right一定是指向target最右边的，因为此时left已经大于right退出循环了。道理同上。

但是当nums中不存在目标值时，要考虑以下三种情况：

target大于所有nums

此时， left会越界

target 小于所有nums

此时right会越界

target在nums中某两个值中间

不会越界，但是left，right都不是指向target

但此时只需要关注right即可，如果right没有越界，直接判断以下right==target就知道结果了