2022-12-07Day1 704二分查找，27移除元素

704二分查找

题目链接：704. 二分查找 - 力扣（Leetcode）

二分查找适用于已排好序的数组，给出一个数组和一个元素，若数组中存在该元素，返回元素索引，若不存在则返回-1.
二分查找具体实现框架包含四个部分：
1 确定查找区间的左右开闭情况

左闭右闭： left,right = 0,len(size)-1  
左闭右开： left,right = 0,len(size)     

2循环退出条件

左闭右闭：while left <= right:   #因为[1,1]区间合法
左闭右开：while left < right:    #因为[1,1)区间不合法，所以[1,2)

3确定中间值

mid = (left+right)//2   #//是为了防止溢出

4中间值与目标值的比较

如果中间值比目标值小;
if  nums[mid] < target: #要找的数比中间索引的元素值大，[left,mid)
  right = mid #左闭右开情况
else: 
   left = mid+1   #[mid+1,right)

704 完整实现代码：

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

二分法循环体结束后其实left=right=mid，都可以返回
35.搜索插入位置 和 34. 在排序数组中查找元素的第一个和最后一个位置 ，主要是利用返回值，对返回值进行处理的一点小变动

27移除元素

题目链接：27. 移除元素 - 力扣（Leetcode）

第一次接触快慢指针的概念

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        fast = 0 #快指针获取新数组中的元素
        slot = 0 #慢指针获取新数组中的位置
        for fast in range(len(nums)):
            if nums[fast] != val:  #这步可以实现如果是要找的元素，fast更新，但slot不更新，即元素往后一个了，但是地址不变，所以后面的元素把前面的元素覆盖了，这样就实现了移除
                nums[slot] = nums[fast]
                slot +=1
        return slot

数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。
存在疑惑的地方：定义的slot明明是一个数，但是返回的是一个列表。
需要明天继续消化下相关题型。