704. 二分查找 - 力扣（LeetCode）
經(jīng)典二分查找弓颈，找區(qū)間邊界是難點
解題思路
依據(jù)升序數(shù)組區(qū)間中間數(shù)和目標(biāo)的大小關(guān)系哆致，不斷縮小搜索區(qū)間
方法一 左閉右閉
class Solution:
def search(self, nums: List[int], target: int) -> int:
# 左閉右閉
left = 0
right = len(nums)-1
while left <= right:
middle = left + (right - left) // 2
if nums[middle] < target:
left = middle + 1 #這里寫left = middle 會超出時間限制
elif nums[middle] > target:
right = middle - 1
else:
return middle
return -1
方法二 左閉右開
class Solution:
def search(self, nums: List[int], target: int) -> int:
# 左閉右開
left = 0
right = len(nums)
while left < right:
middle = left + (right - left) // 2
if nums[middle] < target:
left = middle + 1
elif nums[middle] > target:
right = middle
else:
return middle
return -1
- 確定好區(qū)間邑商，不要遺漏或者越界摄咆，法一法二差別不大
- mid = (left+right)//2 可能會上溢出
- mid 的寫法參考了算法記錄 | Day1數(shù)組基礎(chǔ) - 掘金 (juejin.cn)
27. 移除元素 - 力扣（LeetCode）
數(shù)組的元素在內(nèi)存地址中是連續(xù)的，不能單獨刪除數(shù)組中的某個元素人断，只能覆蓋吭从。采用雙指針的方法
代碼隨想錄 (programmercarl.com)
解題思路
在原始數(shù)組上覆蓋新數(shù)組，遇到需要刪除的數(shù)就跳過
方法一
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
fast, slow = 0, 0
while fast < len(nums):
if nums[fast] != val:
nums[slow] = nums[fast]
slow = slow + 1
fast = fast + 1
return slow
- 快指針指向的是需要加入新數(shù)組的元素恶迈，遇到需要刪除的元素就跳過涩金；
- 慢指針指向的是新數(shù)組的位置
另一種方法（忘了哪里看來的題解）
因為此題元素的順序可以改變，所以雙指針可理解為左指針和右指針暇仲，左指針指向新數(shù)組的位置步做，若當(dāng)前位置的元素不等于需要刪除的元素就跳過，否則就用右指針的元素替換奈附。
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
a = 0
b = len(nums)
while a<b:
if nums[a] ==val:
nums[a] = nums[b-1]
b = b-1
else:
a = a+1
return a
