704.二分查找

链接 思路：二分法。注意边界条件，左闭右闭还是左闭右开。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

时间复杂度：O(logn)

27.移除元素

链接 思路：快慢指针。fast代表数组中符合条件的元素，不包含目标元素。slow代表新数组的下标位置。

1
2
3
4
5
6
7
8
9

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

时间复杂度：O(n)