二分查找

  • 二分查找框架

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution:
        def binary_search(self, nums: list, target: int):
            left, right = 0, ...
            while ...:
                mid = int(left + (right - left) / 2)
                if nums[mid] < target:
                    left = ...
                elif nums[mid] > target:
                    right = ...
                elif nums[mid] == target:
                    ...
            return ...

  • 技巧：不要出现else，而是把所有情况用else if写清楚，这样可以清楚地展现所有细节

  • 寻找一个数（基本的二分搜索）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution:
        def binary_search(self, nums: list, target: int):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = int(left + (right - left) / 2)
                if nums[mid] < target:
                    left = mid + 1
                elif nums[mid] > target:
                    right = mid - 1
                elif nums[mid] == target:
                    return mid
            return -1
    • 思路：
      • 因为right赋值为len(nums)-1，所以相当于每次的搜索区间为左闭右闭区间，即[left, right]
      • 所以，while条件为left <= right，其中right最大为数组长度
      • 什么时候终止？终止条件为left = right + 1，即[right+1, right]，这时候区间为空
      • 因为是闭区间，所以当mid不满足条件时，下个搜索位置就需要排除mid，即mid+1或mid-1

  • 寻找左侧边界的二分搜索

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution:
        def left_bound(self, nums: list, target: int):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = int(left + (right - left) / 2)
                if nums[mid] < target:
                    left = mid + 1
                elif nums[mid] > target:
                    right = mid - 1
                elif nums[mid] == target:
                    right = mid - 1
            if left >= len(nums) or nums[left] != target:
                return -1
            return left
    • 思路：
      • 能够搜索左侧边界：关键在于，当nums[mid]=target时，不返回结果，而是收缩右侧边界，使得区间不断向左收缩，达到锁定左侧边界的目的
      • while终止条件是left=right+1，即[right+1, right]
      • 注意临界条件的判断，target比所有数都大的情况，left的下标超过数组长度，返回-1

  • 寻找右侧边界的二分搜索

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution:
        def right_bound(self, nums: list, target: int):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = int(left + (right - left) / 2)
                if nums[mid] < target:
                    left = mid + 1
                elif nums[mid] > target:
                    right = mid - 1
                elif nums[mid] == target:
                    left = mid + 1
            if right < 0 or nums[right] != target:
                return -1
            return right
    • 思路：
    • 能够搜索左侧边界：关键在于，当nums[mid]=target时，不返回结果，而是收缩左侧边界，使得区间不断向右收缩，达到锁定右侧边界的目的
      • while终止条件是left=right+1，即[right+1, right]
      • 注意临界条件的判断，target比所有数都小的情况，right的下标小于0，返回-1