二分查找

二分的本质：二段性 看到有序，找最大、最小值，LeetCode周赛第三题：首先考虑二分查找。

板子题

209. Minimum Size Subarray Sum

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        cur = 0
        res = inf
        i = 0
        for j in range(len(nums)):
            cur += nums[j]
            if cur < target:
                continue
            while cur >= target:
                res = min(res, j - i + 1)
                cur -= nums[i] 
                i += 1
        return res if res != inf else 0

• 时间复杂度：
• 空间复杂度：

应用题

744. Find Smallest Letter Greater Than Target

看到有序，首先考虑二分。注意当left和right指针最后落在数组尾部（即index == n）时，取数组首个元素。

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        n = len(letters)
        left, right = 0, n
        while left < right:
            mid = left + right >> 1
            if letters[mid] <= target:
                left = mid + 1
            else:
                right = mid
        return letters[0] if left == n else letters[left]

• 时间复杂度：
• 空间复杂度：

875. Koko Eating Bananas

若在每小时能够吃下根香蕉的前提下，能够在小时内吃完所有香蕉（按pile分配），则所有均是符合题意的进食速度；要求其最小值。
中，以为分割线（二段性），其实上是以二分思想求其lower_bound

from math import ceil
class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        # 以每小时'k'的速度进食，能否在'h'小时内吃完所有香蕉
        def check(k):
            return sum(ceil(p / k) for p in piles) <= h
        left, right = 1, max(piles)  # 上界max(piles): 每小时只能选择一堆香蕉
        while left < right:
            mid = left + right >> 1
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return left

• 时间复杂度：，其中是香蕉总堆数，是堆中最大香蕉数量
• 空间复杂度：

其中，天花板÷也可写为：

def ceil_divide(p, k):
    return (p - 1) // k + 1

1011. Capacity To Ship Packages Within D Days

设船只的运载能力为，凡是大于的均能在给定时间内运载完所有货物；反之亦然。（二段性）
，求以为分割点的lower_bound。

• 下界：，同一批货物不能拆分
• 上界：，即一天运完所有货物

其中check()方法的编写值得思量。

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        # 当前运载能力为'c'，能否在'D'天内按顺序、不拆分地运载完所有货物
        def check(c):
            days = 1
            cur = 0
            for weight in weights:
                if cur + weight > c:
                    days += 1
                    cur = 0
                cur += weight
            return days <= D
        left, right = max(weights), sum(weights)
        while left < right:
            mid = left + right >> 1
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return left

• 时间复杂度：，其中是货物总数，是货物的质量之和
• 空间复杂度：

5219. Maximum Candies Allocated to K Children

设给每个孩子分配个糖果能够满足要求，那么凡是小于的糖果分配数也能满足要求；反之亦然。二段性
，以为分割点，寻找upper_bound。

class Solution:
    def maximumCandies(self, candies: List[int], k: int) -> int:
        # 每人分'm'个糖果（可拆分，不可合并），能否满足'k'个孩子的需求
        def check(m):
            num_satisfy = 0
            for candy in candies:
                num_satisfy += candy // m
                if num_satisfy >= k:
                    return True
            return False
        left, right = 1, sum(candies) // k
        if left > right:                    # 特判：每人一个也不够分
            return 0
        while left < right:
            mid = left + right + 1 >> 1     # 寻找upper_bound
            if check(mid):
                left = mid
            else:
                right = mid - 1
        return left

• 时间复杂度：，其中是糖果总堆数，是糖果的数量之和
• 空间复杂度：

2187. Minimum Time to Complete Trips

设给定时间，并行的车辆能够完成给定的旅途数目，那么所有大于的时间也满足要求；反之亦然。二段性
，以为分割点，寻找lower_bound。

• 下界：跑得最快的车（单趟耗时最短）完成趟旅途所花费的时间

• 上界：跑得最快的车（单趟耗时最短）完成total_trips旅途所花费的时间

  class Solution:
    def minimumTime(self, times: List[int], total_trips: int) -> int:
        # 消耗时间't'，并行的线路能够完成的旅途是否大于或等于'total_trips'
        def check(t):
            return sum(t // time for time in times) >= total_trips
        left, right = min(times), min(times) * total_trips
        while left < right:
            mid = left + right >> 1
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return left

• 时间复杂度：，其中是车辆数目，是车辆最少完成时间，是总趟数

• 空间复杂度：

162. Find Peak Element

预处理nums = [-inf] + nums + [-inf]后线性扫描，不符合题设的时间复杂度；考虑二分查找。
易证：

1. 对于任意数组（左右两侧填充），一定存在峰值；
2. 对于一个满足的位置， 的右边一定存在峰值；或对于一个满足的位置，的左边一定存在峰值。

   最早在 33. 搜索旋转排序数组 中，我们强调，二分的本质是「二段性」而非「单调性」，而经过本题，我们进一步发现「二段性」还能继续细分，不仅仅只有满足 **01 特性**（满足/不满足）的「二段性」可以使用二分，满足 **1? 特性**（一定满足/不一定满足）也可以二分。

   • 往上坡方向走，一定能找到山峰；
   • 往下坡方向走，可能找到山峰。

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1

        while left < right:
            mid = left + right >> 1
            if nums[mid] > nums[mid+1]:
                right = mid
            else:
                left = mid + 1

        return left

• 时间复杂度：
• 空间复杂度：

4. Median of Two Sorted Arrays

容易想到的直观解法如下，时间复杂度：

1. 将两个有序数组合并为一个有序数组，再寻找中位数。 空间复杂度
2. 不需要显示合并，利用双指针 + 数组长度找到中位数位置。 空间复杂度

考虑使用两个数组的**有序**特性：由于已知数组长度，可将寻找中位数的过程转化为求第大的元素。
使用二分查找的思想，不断将一分为二，从两个数组的头部隐式移除（用offset表征）个元素，直到找到第个元素。注意三种特殊情况的判断。

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:

        def get_Kth_element(k):
            offset_1, offset_2 = 0, 0
            while 1==1:
                if offset_1 == m:
                    return nums2[offset_2 + k - 1]
                if offset_2 == n:
                    return nums1[offset_1 + k - 1]
                if k == 1:
                    return min(nums1[offset_1], nums2[offset_2])

                index_1 = min(offset_1 + k//2 - 1, m - 1)  # 若越界，取末尾元素
                index_2 = min(offset_2 + k//2 - 1, n - 1)
                if nums1[index_1] < nums2[index_2]:
                    k -= index_1 - offset_1 + 1            # k减去该段长度，而非'k//2'
                    offset_1 = index_1 + 1
                else:
                    k -= index_2 - offset_2 + 1
                    offset_2 = index_2 + 1

        m, n = len(nums1), len(nums2)
        k1, k2 = (m + n + 1) // 2, (m + n + 2) // 2        # 统一'奇\偶'写法
        return (get_Kth_element(k1) + get_Kth_element(k2)) / 2

• 时间复杂度：
• 空间复杂度：

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:

        # k => 1-index
        def get_Kth_element(k) -> int:
            i = j = 0
            while 1 != 0:
                if i == m:
                    return nums2[j + k - 1]
                if j == n:
                    return nums1[i + k - 1]
                if k == 1:
                    return min(nums1[i], nums2[j])

                if nums1[i] < nums2[j]:
                    i += 1
                else:
                    j += 1
                k -= 1

        m, n = len(nums1), len(nums2)
        k1, k2 = (m+n+1)//2, (m+n+2)//2
        return (get_Kth_element(k1) + get_Kth_element(k2)) / 2

• 时间复杂度：
• 空间复杂度：

540. Single Element in a Sorted Array

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + right >> 1
            if mid & 1:  # 奇数下标
                if nums[mid] == nums[mid+1]:
                    right = mid
                else:
                    left = mid + 1
            else:        # 偶数下标
                if nums[mid] == nums[mid+1]:
                    left = mid + 1
                else:
                    right = mid
        return nums[left]

• 时间复杂度：
• 空间复杂度：

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + right >> 1
            if nums[mid] == nums[mid ^ 1]:
                left = mid + 1
            else:
                right = mid
        return nums[left]

• 时间复杂度：
• 空间复杂度：