代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素。

704. 二分查找

1. 有顺序
   2.左右 双指针
2. 通过中间位大小来判断指针移动
   难点：

• 边界
• 防止溢出错误： mid = left + (right - left) //2
  Complexity: O(log(n))

class Solution: def search(self, nums: List[int], target: int) -> int: # sorted list # binary search left = 0 right = len(nums) - 1 while left <= right: mid = left + (right - left) //2 if nums[mid] < target: left += 1 elif nums[mid] > target: right -= 1 else: return mid return -1

27. 移除元素
快慢指针
快指针用来搜索， 慢指针用来更新内容。
关键点：nums[slow] = nums[fast]
Complexity: O(n)

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        fast, slow = 0, 0
        count = 0
        while fast < len(nums):
            if nums[fast]!= val:
                nums[slow] = nums[fast]
                slow += 1
                count += 1
            fast += 1
        return count