二分查找（Binary Search）是一种在有序数组中查找特定元素的搜索算法。其基本思想是将待查找的键值与数组中间的元素进行比较，如果两者相等，则查找成功；如果待查找的键值小于中间元素，则在数组的左半部分继续查找；如果待查找的键值大于中间元素，则在数组的
摘要：二分查找 (1) 搜索插入位置 """ 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
二分查找
(1) 搜索插入位置
"""
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
"""
left = 0
right = len(nums)-1
while left <= right:
mid = (left+right)//2
if nums[mid] < target:
left = mid+1
else:
right = mid-1
return left
(2) 在排序数据中查找元素范围
"""
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。
"""
def get_index(nums, target):
left, right = 0, len(nums)-1
while left <= right:
mid = (left+right)//2
if nums[mid] < target:
left = mid+1
else:
right = mid-1
return left
if target not in nums:
return [-1, -1]
start = get_index(nums, target)
end = get_index(nums, target+1)-1
return [start, max(start, end)]
(3) 搜索旋转排序数组
"""
整数数组 nums 按升序排列，数组中的值互不相同 。在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 向左旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2]。给你旋转后的数组 nums 和一个整数 target，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1。
"""
left, right = 0, len(nums)-1
while left <= right:
mid = (left+right)//2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid-1
else:
left = mid+1
else:
if nums[mid] < target <= nums[right]:
left = mid+1
else:
right = mid-1
return -1
(4) 寻找旋转排序数组的最小值
"""
给你一个元素值 互不相同 的数组 nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素 。
"""
left, right = 0, len(nums)-1
while left <= right:
mid = (left+right)//2
if nums[mid] >= nums[0]:
left = mid+1
else:
right = mid-1
return nums[left] if left < len(nums) else nums[0]
(5) 寻找两个正序数组的中位数
"""
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。