題目704.二分查找（兩個前提：1.有序數(shù)組颅夺；2.無重復(fù)元素）
示例1：
輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現(xiàn)在 nums 中并且下標為 4
關(guān)鍵點：
1. 區(qū)間搜索的時候要明確區(qū)間定義：左閉右閉[]還是左閉右開[)朋截？左開右閉比較少見。吧黄。
2. 邊界處理部服，left<right還是left<=right,right=middle還是right=middle-1
3. 循環(huán)中根據(jù)區(qū)間定義做邊界處理，就是循環(huán)不變量規(guī)則：在while循環(huán)中堅持一個區(qū)間拗慨，區(qū)間即不變量
# 左閉右閉廓八，合法區(qū)間的話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
# 左閉右開， 合法區(qū)間的話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 #假如原數(shù)組沒有該target赵抢，left位置為要插入的位置
題目27.移除元素
1. 限制O(1)的空間復(fù)雜度
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右邊是開區(qū)間剧蹂，因此取不到，所以j=len(nums)而不是len(nums)-1
nums[k-1] = nums[k]
i -= 1 #因為元素被刪掉之后烦却，還要從當前位置開始查找宠叼，因此這里-1
j -= 1
i += 1
return j
## 雙指針法
1. 用雙指針代替一層for循環(huán)，相比于暴力解法的O(n^2)的時間復(fù)雜度短绸，雙指針可降低到O(n)的時間復(fù)雜度
2. 快指針用來尋找新數(shù)組所需要的元素
3. 慢指針用來定位要更新的位置
slow = fast = 0
for i in range(0, len(nums)):
if nums[i] != val:
nums[slow] = nums[fast]
slow += 1
return slow
