704. 二分查找 - 力扣（LeetCode）

经典二分查找，找区间边界是难点

解题思路

依据升序数组区间中间数和目标的大小关系，不断缩小搜索区间

方法一 左闭右闭

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

• 确定好区间，不要遗漏或者越界，法一法二差别不大
• mid = (left+right)//2 可能会上溢出
• mid 的写法参考了算法记录 | Day1数组基础 - 掘金 (juejin.cn)

27. 移除元素 - 力扣（LeetCode）

数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。采用双指针的方法
代码随想录 (programmercarl.com)

解题思路

在原始数组上覆盖新数组，遇到需要删除的数就跳过

方法一

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

• 快指针指向的是需要加入新数组的元素，遇到需要删除的元素就跳过；
• 慢指针指向的是新数组的位置

另一种方法（忘了哪里看来的题解）

因为此题元素的顺序可以改变，所以双指针可理解为左指针和右指针，左指针指向新数组的位置，若当前位置的元素不等于需要删除的元素就跳过，否则就用右指针的元素替换。

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