题目704.二分查找（两个前提：1.有序数组；2.无重复元素）
示例1：
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
关键点：
1. 区间搜索的时候要明确区间定义：左闭右闭[]还是左闭右开[)？左开右闭比较少见。。
2. 边界处理，left<right还是left<=right,right=middle还是right=middle-1
3. 循环中根据区间定义做边界处理，就是循环不变量规则：在while循环中坚持一个区间，区间即不变量
# 左闭右闭，合法区间的话left可能等于right
left = 0, right = numsize - 1, target
while(left <= right)：
middle = (left + right)/2
if nums[middle] > target:
right = middle - 1
else if nums[middle] < target:
left = middle + 1
else
return middle
return -1
# 左闭右开， 合法区间的话left要小于right
left = 0, right = numsize, target
while(left < right)：
middle = (left + right)/2
if nums[middle] > target:
right = middle
else if nums[middle] < target:
left = middle + 1
else
return middle
return -1
题目35.搜索插入位置
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums)-1
while left <= right:
middle = (left + right) // 2
if nums[middle] > target:
right = middle - 1
elif nums[middle] < target:
left = middle + 1
else:
return middle
return left #假如原数组没有该target，left位置为要插入的位置
题目27.移除元素
1. 限制O(1)的空间复杂度
2.
## 暴力解法
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
i, j = 0, len(nums)
while i < j:
if nums[i] == val:
for k in range(i+1, j): #range右边是开区间，因此取不到，所以j=len(nums)而不是len(nums)-1
nums[k-1] = nums[k]
i -= 1 #因为元素被删掉之后，还要从当前位置开始查找，因此这里-1
j -= 1
i += 1
return j
## 双指针法
1. 用双指针代替一层for循环，相比于暴力解法的O(n^2)的时间复杂度，双指针可降低到O(n)的时间复杂度
2. 快指针用来寻找新数组所需要的元素
3. 慢指针用来定位要更新的位置
slow = fast = 0
for i in range(0, len(nums)):
if nums[i] != val:
nums[slow] = nums[fast]
slow += 1
return slow
