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

#左闭右开
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l=len(nums)
        left=0
        right=l
        if left==0 and nums[0]==target:
            return 0
        while left < right:
            middle=(left+right)//2
            if target>nums[middle]:
                left=middle+1
            elif target<nums[middle]:
                right=middle
            else:
                return middle
        return -1

和左闭右闭时不同,这里的right应该是len(nums),而不是len(nums)-1,因为在左闭右开时,左区间的右端点为右区间的左端点,而且这样能保证left<right.

#左右指针错误解法
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        l=len(nums)
        left=0
        right=l-1
        if right==0 and nums[left]==val:
            return 0
        elif right==0 and nums[left]!=val:
            return 1
        while left<right:
            while nums[right]==val:
                right -=1
                if right<left:
                    return left+1
            while nums[left]!=val:
                left+=1
            nums[left],nums[right]=nums[right],nums[left]
            left+=1
            right-=1
        return left+1

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        l=len(nums)
        left=0
        right=l-1
  
        while left<=right:
            while left<=right and nums[right]==val:
                right -=1
            while left <=right and nums[left]!=val:
                left+=1
            if left<right:
                nums[left]=nums[right]
                left+=1
                right-=1

        return left

在while中加上if判断条件是为了防止出现[2,2,2],val=2的情况.