二分查找
二分查找的模板代码：
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1 # 定义 target 在左闭右闭的区间里，[left, right]
while left <= right:
middle = left + (right - left) // 2
if nums[middle] > target:
right = middle - 1 # target 在左区间，所以 [left, middle - 1]
elif nums[middle] < target:
left = middle + 1 # target 在右区间，所以 [middle + 1, right]
else:
return middle # 数组中找到目标值，直接返回下标
return -1 # 未找到目标值大约 3 分钟