446_二分查找面试题¶

# 模板1：找精确值（最基础）
def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:                   # 注意：<=
        mid = left + (right - left) // 2  # 防溢出写法
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# 模板2：找左边界（第一个>=target的位置）
def lower_bound(nums, target):
    left, right = 0, len(nums)             # 注意：right = len(nums)
    while left < right:                    # 注意：<
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid                    # 不排除mid
    return left                            # left就是下界

# 模板3：找右边界（最后一个<=target的位置）
def upper_bound(nums, target):
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left - 1                        # 最后一个<=target的位置

def search_rotated(nums, target):
    """
    思路：虽然旋转了，但每次 mid 必然把数组分成：
    一半有序 + 一半无序
    判断 target 是否在有序那半，从而收缩范围
    """
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:            # 找到了
            return mid

        # 判断左半 [left, mid] 是否有序
        if nums[left] <= nums[mid]:
            # 左半有序：判断target是否在左半范围内
            if nums[left] <= target < nums[mid]:
                right = mid - 1            # target在左半，去左边
            else:
                left = mid + 1             # target在右半，去右边
        else:
            # 右半 [mid, right] 有序
            if nums[mid] < target <= nums[right]:
                left = mid + 1             # target在右半，去右边
            else:
                right = mid - 1            # target在左半，去左边

    return -1                              # 没找到

# 测试
print(search_rotated([4,5,6,7,0,1,2], 0))  # 4
print(search_rotated([4,5,6,7,0,1,2], 3))  # -1
print(search_rotated([1], 0))              # -1

def search_range(nums, target):
    """
    两次二分：第一次找左边界，第二次找右边界
    """
    def find_left(nums, target):
        """找第一个等于target的位置"""
        left, right = 0, len(nums)
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid                # 等于也往左收缩
        return left                        # left是第一个>=target的位置

    def find_right(nums, target):
        """找最后一个等于target的位置"""
        left, right = 0, len(nums)
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] <= target:
                left = mid + 1             # 等于也往右扩张
            else:
                right = mid
        return left - 1                    # left-1是最后一个<=target的位置

    left_idx = find_left(nums, target)
    right_idx = find_right(nums, target)

    # 验证找到的位置确实等于target
    if left_idx < len(nums) and nums[left_idx] == target:
        return [left_idx, right_idx]
    return [-1, -1]                        # 不存在

# 测试
print(search_range([5,7,7,8,8,10], 8))    # [3, 4]
print(search_range([5,7,7,8,8,10], 6))    # [-1, -1]
print(search_range([], 0))                # [-1, -1]

def find_peak_element(nums):
    """
    思路：如果 mid 右边比 mid 大，则右边一定有峰值（单调递增要么有峰，要么末尾是峰）
    如果 mid 左边比 mid 大，则左边一定有峰值
    """
    left, right = 0, len(nums) - 1

    while left < right:
        mid = left + (right - left) // 2

        if nums[mid] < nums[mid + 1]:      # 右边更高，峰在右边（含mid+1）
            left = mid + 1
        else:                              # 左边更高或相等，峰在左边（含mid）
            right = mid

    return left                            # left == right，就是峰值位置

# 测试
print(find_peak_element([1,2,3,1]))     # 2（nums[2]=3是峰值）
print(find_peak_element([1,2,1,3,5,6,4]))  # 1或5

import bisect

# Python bisect 模块速查
nums = [1, 3, 3, 5, 7]
bisect.bisect_left(nums, 3)    # 1  第一个>=3的位置
bisect.bisect_right(nums, 3)   # 3  第一个>3的位置
bisect.insort_left(nums, 4)    # 插入4，保持有序

# 二分答案模板（最大化最小值/最小化最大值）
def can_achieve(mid):           # 检查答案mid是否可行
    # ... 业务逻辑
    return True/False

left, right = min_possible, max_possible
while left < right:
    mid = (left + right) // 2
    if can_achieve(mid):
        left = mid + 1          # 可行，尝试更大
    else:
        right = mid             # 不可行，降低答案
answer = left - 1              # 或left，看具体情况