今天做的三道题都是与二分法相关。
二分法主要适用于数组已排序的情况，通过减少遍历的情况，提高计算效率。
二分法通用处理方法：
1）定义左边界（left）、右边界(right)、中间位置(（left+right）//2)
2）whlie循环：当左边界 小于（或小于等于）右边界时，进行接下来的计算。是否需要取等号，考虑left=right的情况能否满足条件即可（貌似是句废话，我目前是这样想的...）
- 判断查找出现的不同情况：a.等于中间位置（或中间位置的值）;b.小于中间位置（或中间位置的值）取[左边，中间]；c.大于中间位置（或中间位置的值）取[中间，右边]；
难点：边界值的确定
具体题目：
1.给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
示例
输入: nums = [1,3,5,6], target = 5
输出: 2
明确有哪些情况：
这个题目包含了
(1) 目标值比列表元素最小值更小；
(2) 目标值比列表元素最大值更大;
(3) 目标值是列表中的某一个元素(是第一个元素、最后一个元素、中间任意一个元素)；
(4) 目标值在元素最大值和最小值之间，但不等于任何一个元素
def searchInsert(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums)-1 #保证nums[right]不越界
if target <= nums[0]: #比最小值小或者等于最小值（因为都是插入到位置0上所以可以合并写）
return 0
if target == nums[-1]: #等于最大值
return right
if target > nums[-1]: #比最大值大
return right+1
while left <= right: #while循环判断
mid = (left+right) //2 #提取中间位置
if target == nums[mid]: #如果恰好等于中间值
return mid
elif target < nums[mid]:
right = mid-1
elif target > nums[mid]:
left = mid +1
return left #最后剩下(a,b)，但目标值介乎a和b之间 不等于任何一个，且前面的循环令了left=mid+1 所以可以写成返回left
