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

704-二分查找

• 看到题目的第一想法是创建一个mid变量作为target的比较参考，根据target和nums[mid]的大小关系决定二分后继续搜索的区域范围。
• 随后第一反应是left为0，right为len(nums)-1，和索引一一对应,mid = right-left+1,左闭右开，也就是对于每次二分后的区域为[left,mid)和[mid,right]。递归结束条件为若nums[mid]==target则返回mid，如果left>=right则返回-1.
• 但是在报错后想到一个问题，right的索引最大为len(nums)-1，也是可以被搜索到的位置，如果设为开区间就永远搜索不到，使用递归的时候就会无限套娃。
• 结合代码随想录，想到了问题点不在如何开如何闭，而是要去做对应的处理。这道题左闭右闭也可以：每次二分后的区域为[left,mid]和[mid+1,right]，若采用左闭右开则为：每次二分后的区域为[left,mid)和[mid，right+1)。显然我原本的思路更贴近第二种。所以在此基础上使得最开始的right赋值为len(nums)，创造出一个专门用来做开区间边界的冤大头即可。

class Solution:
    def sub_search(self,nums:List[int],target:int,left:int,right=int):
        mid = left+(right-left)//2
        if left >= right:
            return -1
        elif target == nums[mid]:
            return mid
        elif target < nums[mid]:
            print('<',left,mid,right)
            return self.sub_search(nums,target,left=left,right=mid)
        else:
            print('>',left,mid,right)
            return self.sub_search(nums,target,left=mid+1,right=right)

    def search(self, nums: List[int], target: int) -> int:
        left,right = 0,len(nums)
        return self.sub_search(nums,target,left,right)
        

27-移除对象

• 第一反应是使用pop和remove这样的方法，但是想到这里考核的点在于数组是连续存储，也就是移除对象之后不能留有空缺
• 简单的肯定暴力，时间空间复杂度都是O(n^2)，所以使用快慢指针的方法， 使用快慢指针有三种情况：
  1. 结束，也就是fast指针指完了末尾，即fast>=len(nums)
  2. 快、慢指针都前进，即fast+=1，slow+=1，条件是nums[fast]!=val
  3. 快指针前进，慢指针不动，相当于快指针用来遍历，慢指针用来返回一个剔除指定val数量的值
  4. 如果做双向链表应该也可以用这个思路。

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