07 二分搜索 · Interview Prep

QR 对对数复杂度敏感

🔖 #33 · Search in Rotated Sorted Array ★

难度: Medium | 标签: Binary Search | 链接: https://leetcode.com/problems/search-in-rotated-sorted-array/

题目描述

在旋转排序数组中搜索目标值。

解题思路

判断 mid 在哪层有序的半段，再判断 target 是否在该有序半段内。

答案代码


def search(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] == target:
            return mid
        if nums[l] <= nums[mid]:  # 左半有序
            if nums[l] <= target < nums[mid]:
                r = mid - 1
            else:
                l = mid + 1
        else:  # 右半有序
            if nums[mid] < target <= nums[r]:
                l = mid + 1
            else:
                r = mid - 1
    return -1

扩展总结

变体：#81 包含重复元素的旋转数组（需处理 nums[l]==nums[mid]）

#153 Find Minimum in Rotated Sorted Array — 找旋转点

🔖 #4 · Median of Two Sorted Arrays ★

难度: Hard | 标签: Binary Search | 链接: https://leetcode.com/problems/median-of-two-sorted-arrays/

题目描述

找两个已排序数组的中位数，要求 O(log(m+n))。

解题思路

对较短数组二分，找分割点使左半达到 (m+n)//2 个元素，并满足左半元素均小于右半。

答案代码


def findMedianSortedArrays(nums1, nums2):
    A, B = nums1, nums2
    if len(A) > len(B):
        A, B = B, A
    m, n = len(A), len(B)
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2
        j = (m + n + 1) // 2 - i
        Aleft = A[i-1] if i > 0 else float('-inf')
        Aright = A[i] if i < m else float('inf')
        Bleft = B[j-1] if j > 0 else float('-inf')
        Bright = B[j] if j < n else float('inf')
        if Aleft <= Bright and Bleft <= Aright:
            if (m + n) % 2:
                return max(Aleft, Bleft)
            return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
        elif Aleft > Bright:
            hi = i - 1
        else:
            lo = i + 1

扩展总结

经典难题，考察对二分的深度理解

默记：始终对较短的数组做二分

🔖 #410 · Split Array Largest Sum

难度: Hard | 标签: Binary Search, DP | 链接: https://leetcode.com/problems/split-array-largest-sum/

题目描述

将数组分为 k 个子数组，使最大子数组和最小化。

解题思路

二分答案：答案范围是 [max(nums), sum(nums)]，对答案二分，验证是否能用 k 次分割实现。

答案代码


def splitArray(nums, k):
    def check(mid):
        parts = count = 1
        for n in nums:
            count += n
            if count > mid:
                parts += 1
                count = n
                if parts > k:
                    return False
        return True
    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if check(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

扩展总结

「最小化最大值」模型 = 二分答案经典应用

相关：#875 Koko Eating Bananas、#1011 Capacity to Ship Packages