力扣704.二分查找
二分查找步骤：
如果目标值等于中间元素，则找到目标值。
如果目标值小于中间元素，继续在左侧搜索。
如果目标值大于中间元素，则继续在右侧搜索。
如果最终搜索区间的左右节点重合也未找到，则表明不存在该值返回-1
时间复杂度：O(logN)
非递归方法实现
def search(nums, target):start, end = 0, len(nums)-1while start < end:mid = start + (end - start)//2if target == nums[mid]:return midif target < nums[mid]:end = mid - 1else:start = mid + 1return -1nums = [-1, 0, 3, 5, 9, 12]target = 9print(search(nums, target))# 输出4
递归方法实现
def search(nums, target):def bs(i, j):if i > j:return -1 # 设置终止条件m = (i + j) // 2if target == nums[m]:return melif target < nums[m]:return bs(i, m - 1)else:return bs(m + 1, j)return bs(0, len(nums) - 1)