[数据结构与算法]二分搜索模板--Python

二分法核心点

1. 确定搜索的范围和区间
2. 取中间的数判断是否满足条件
3. 如果不满足条件，判定应该往哪个半边继续搜索

二分搜索根据模板，只需要修改判断条件即可

递归写法

def binary_search_recursive(nums, target, low, high):
    """
    在nums的low到high下标的闭区间中搜索target
    :param nums:
    :param target:
    :param low:
    :param high:
    :return:
    """
    if low > high:
        return -1

    middle = low + int((high - low) / 2)  # (low + high)/2会导致溢出？

    if nums[middle] == target:
        return middle

    if target < nums[middle]:
        return binary_search_recursive(nums, target, low, middle - 1)
    return binary_search_recursive(nums, target, middle + 1, high)

非递归写法

def binary_search_not_recursive(nums, target, low, high):
    while low <= high:
        middle = low + int((high - low) / 2)

        if nums[middle] == target:
            return middle

        if target < nums[middle]:
            high = middle - 1
        else:
            low = middle + 1
    return -1

题型

1.找确定的边界,如leetcode 34

def search_lower_bound(nums, target, low, high):
    if low > high:
        return -1

    middle = low + int((high - low) / 2)

    # 与模板的差异只在判断条件
    if nums[middle] == target and (middle == 0 or nums[middle - 1] < target):
        return middle

    if target <= nums[middle]:
        return search_lower_bound(nums, target, low, middle - 1)
    return search_lower_bound(nums, target, middle + 1, high)


def search_upper_bound(nums, target, low, high):
    if low > high:
        return -1

    middle = low + int((high - low) / 2)

    if nums[middle] == target and (middle == len(nums) - 1 or nums[middle + 1] > target):
        return middle

    if target <= nums[middle]:
        return search_upper_bound(nums, target, low, middle - 1)
    return search_upper_bound(nums, target, middle + 1, high)

模糊的边界

# 第一个大于target的数
def first_greater_than(nums, target, low, high):
    if low > high:
        return None

    middle = low + int((high - low) / 2)

    if nums[middle] > target and (middle == 0 or nums[middle - 1] <= target):
        return middle

    if target < nums[middle]:
        return first_greater_than(nums, target, low, middle - 1)
    return first_greater_than(nums, target, middle + 1, high)


# 最后一个小于target的数
def last_smaller_than(nums, target, low, high):
    if low > high:
        return None

    middle = low + int((high - low) / 2)

    if nums[middle] < target and (middle == len(nums) - 1 or nums[middle + 1] >= target):
        return middle

    if target < nums[middle]:
        return last_smaller_than(nums, target, low, middle - 1)
    return last_smaller_than(nums, target, middle + 1, high)

leetcode33旋转排序数组的搜索

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        low = 0
        high = len(nums) - 1
        return self.binary_search(nums, target, low, high)

    def binary_search(self, nums, target, low, high):
        if low > high:
            return -1

        middle = low + int((high - low) / 2)
        if nums[middle] == target:
            return middle

        # 与标准的binary_search相比，多了一层判断，判断哪边已经排好序
        if nums[low] <= nums[middle]:  # 左边已经排好序
            # 在左边
            if nums[low] <= target and target < nums[middle]:
                return self.binary_search(nums, target, low, middle - 1)
            # 在右边
            return self.binary_search(nums, target, middle + 1, high)
        else:  # 右边已经排好序
            # 在右边
            if nums[middle] < target and target <= nums[high]:
                return self.binary_search(nums, target, middle + 1, high)
            # 在左边
            return self.binary_search(nums, target, low, middle - 1)

不定长的边界

不知道长度的数组

# 1. 一直遍历  -- 低效
# 2. binary  low=0, high=1, high * 2 while logs[high] != null
# when logs[high] == null, 在 [high/2,high]进行二分搜索
def get_upper_bound(logs, high):
    if logs[high] is None:
        return high
    return get_upper_bound(logs, high * 2)


# 确定upper_bound后从0到upper_bound进行binary search
def binary_search(logs, low, high):
    if low > high:
        return -1

    middle = low + int((high - low) / 2)
    # 当前位置为空，而前一个不为空，说明找到边界
    if logs[middle] is None and logs[middle - 1] is not None:
        return middle

    if logs[middle] is None:
        return binary_search(logs, low, middle - 1)
    return binary_search(logs, middle + 1, high)