0 Binary Search Basic

什么是二分查找？

二分查找（Binary Search）是在有序数据中通过每次排除一半来快速定位目标的算法。时间复杂度 O(log n)

适用条件：
- 数据有序（或具有某种单调性/二段性）
- 能通过中间元素判断答案在哪一半
模板一：

1l, r = 0, n - 1          # 闭区间 [l, r]；值域二分时换成 值域下界, 值域上界
2while l < r:
3    mid = (l + r) // 2
4    if check(mid):
5        r = mid          # mid 可能是答案，保留
6    else:
7        l = mid + 1      # mid 一定不是答案，排除
8return l                 # 退出时 l == r

模板二：

1l, r = 0, n - 1          
2while l < r:
3    mid = (l + r + 1) // 2
4    if check(mid):
5        l = mid          
6    else:
7        r = mid - 1      
8return l

二分一定有解，但是不一定是题目的解
- 二分的解一定属于[0, n - 1]，但是答案可能是- 1 or n，在循环外考虑
二分答案的三步套路
- 确认答案可分 ：大了行小了不行(或反过来)
- 写 check(x) ：通常是 O(n) 的模拟或贪心
- 定 l, r 的值域：下界取最小合法值,上界取一个保证可行的值

1 二分模板

1.1 搜索插入位置 | Easy

题目：排序数组 + target,存在返回下标,不存在返回按序插入的位置。要求 O(log n)

思路分析：

思路转换为找第一个>= target的位置，答案可能不在[0, n - 1]，需要额外判断

target in nums：第一个target num的位置就是答案
target not in nums:
- target < max(nums): 插入位置就是第一个> target的位置
- target > max(nums): 插入位置就是最后一个位置n

踩坑记录：

注意模板：r = n - 1 while l < r mid = (l + r) // r; r = mid
需要判断二分答案是不是题目答案

代码：

 1class Solution:
 2    def searchInsert(self, nums: List[int], target: int) -> int:
 3        n = len(nums)
 4        if target > nums[n - 1]:
 5            return n
 6
 7        l, r = 0, n - 1
 8        while l < r:
 9            mid = (l + r) // 2
10            if nums[mid] >= target:
11                r = mid
12            else:
13                l = mid + 1
14        return l

复杂度：

时间O(log n)
空间O(1)

1.2 在排序数组中查找元素的第一个和最后一个位置 | Medium

题目：排序数组(有重复)+ target,返回 [起始位置, 结束位置],不存在返回 [-1, -1]。要求 O(log n)

思路分析：

左边界:套模板A, check nums[mid] >= target
右边界:套模板B(镜像,上取整),check nums[mid] <= target
需要判断二分解与答案解

踩坑记录：

找<= target时，可以从第一段l开始
l = mid $\Rightarrow$ mid = (l + r + 1) // 2
注意边界条件：
- n == 0: [-1, -1]
- target < nums[0] or target > nums[n - 1]: 都可以找到插入位置l，然后再判断nums[l] == target

代码：

 1class Solution:
 2    def searchRange(self, nums: List[int], target: int) -> List[int]:
 3        n = len(nums)
 4        if n == 0:
 5            return [-1, -1]
 6
 7        l, r = 0, n - 1
 8        while l < r:
 9            mid = (l + r) // 2
10            if nums[mid] >= target:
11                r = mid
12            else:
13                l = mid + 1
14        if nums[l] != target:
15            return [-1, -1]
16
17        st, r = l, n - 1
18        while l < r:
19            mid = (l + r + 1) // 2
20            if nums[mid] <= target:
21                l = mid
22            else:
23                r = mid - 1
24        return [st, l]

复杂度：

时间O(log n)(两次二分是常数叠加)
空间O(1)

2 旋转数组

数组本来有序,被从某点「切开、前后交换」了一次: 左段全 > nums[n-1],右段全 <= nums[n-1]，所以我们需要找到分界点

2.1 寻找旋转排序数组中的最小值 | Medium

题目：元素互不相同的旋转升序数组,返回最小元素。要求 O(log n)

思路分析：找第一个<= nums[n - 1]的位置，二分解域和答案解一样

踩坑记录：

没旋转也不需要特判

代码：

 1class Solution:
 2    def findMin(self, nums: List[int]) -> int:
 3        n = len(nums)
 4        l, r = 0, n - 1
 5        while l < r:
 6            mid = (l + r) // 2
 7            if nums[mid] <= nums[n - 1]:
 8                r = mid
 9            else:
10                l = mid + 1
11        return nums[l]

复杂度：

时间O(log n)
空间O(1)

2.2 搜索旋转排序数组 | Medium

题目：元素互不相同的旋转升序数组 + target,存在返回下标,否则返回 -1。要求 O(log n)

思路分析：首先我们需要找到分段点$k$，然后根据$k$判断在哪个区间找$target$

k == 0: 相当于未旋转l, r = 0, n - 1
k > 0:
- 前半段nums[0] <= target <= nums[k - 1]：l, r = 0, k - 1
- 后半段：l, r = k, n - 1

合并一下：

k > 0 and nums[0[ <= target <= nums[k - 1]: l, r = 0, k - 1
else: l, r = k, n - 1

踩坑记录：

不要忘了未旋转这种情况

代码：

 1class Solution:
 2    def search(self, nums: List[int], target: int) -> int:
 3        n = len(nums)
 4        l, r = 0, n - 1
 5        while l < r:
 6            mid = (l + r) // 2
 7            if nums[mid] <= nums[n - 1]:
 8                r = mid
 9            else:
10                l = mid + 1
11        k = l
12
13        if k > 0 and nums[0] <= target <= nums[k - 1]:
14            l, r = 0, k - 1
15        else:
16            l, r = k, n - 1
17
18        while l < r:
19            mid = (l + r) // 2
20            if nums[mid] >= target:
21                r = mid
22            else:
23                l = mid + 1
24        return l if nums[l] == target else -1

复杂度：

时间O(log n)
空间O(1)

3 构造check函数

3.1 寻找峰值 | Medium

题目：峰值 = 严格大于左右相邻。返回任意一个峰值的下标。可假设 nums[-1] = nums[n] = -∞,且 nums[i] != nums[i+1]。要求 O(log n)

思路分析：找一个nums[i] >= nums[i + 1]，多峰不一定是第一个

踩坑记录：

以为条件成立时 mid 就是答案

   [ 1,  5,  4,  3,  2 ]     mid = 2

   nums[2] = 4 > nums[3] = 3   ✓ 条件成立
   但 nums[1] = 5 > 4          ✗ 所以 4 不是峰值

条件只说明「mid 比右邻居大」,没说明比左邻居大。它保证的是「[l, mid] 内有峰值」,不是「mid 是峰值」

代码：

 1class Solution:
 2    def findPeakElement(self, nums: List[int]) -> int:
 3        n = len(nums)
 4
 5        l, r = 0, n - 1
 6        while l < r:
 7            mid = (l + r) // 2
 8            if nums[mid] >= nums[mid + 1]:
 9                r = mid
10            else:
11                l = mid + 1
12        return l

复杂度：

时间O(log n)
空间O(1)

3.2 爱吃香蕉的珂珂 | Medium

题目：n 堆香蕉、h 小时。速度 k 根/小时,每小时选一堆吃 k 根(不足 k 则吃完该堆,这一小时不再吃别的堆)。求 h 小时内吃完的最小速度 k。保证 piles.length <= h

思路分析：没有数组可以二分，需要二分的目标是速度的值域，然后check这个速度是否满足条件：

速度初始最小值是1, 初始最大值是max(piles) 构造check函数：判断当前速度是否可以在$h$小时内吃完

踩坑记录：

check函数构造：math.ceil(p / v) = (p + v - 1) // v

代码：

 1class Solution:
 2    def minEatingSpeed(self, piles: List[int], h: int) -> int:
 3        def check(v):
 4            return sum((p + v - 1) // v for p in piles) <= h
 5
 6        l, r = 1, max(piles)
 7        while l < r:
 8            mid = (l + r) // 2
 9            if check(mid):
10                r = mid
11            else:
12                l = mid + 1
13        return l

复杂度：

时间O(n · log(max(piles))): 二分 log(max) 次,每次 check 遍历 n 堆
空间O(1)

3.3 每个小孩最多能分到多少糖果 | Medium

题目：每堆糖果可切成任意数量的子堆,但不能合并。分给 k 个小孩,每人拿走至多一堆且数量相同。求每人能拿到的最大数量

思路分析：

二分check(num)：当前num能否满足分给所有人
答案分布是：T T T T F F F

踩坑记录：

T T T T F F F: 找最大值l = mid
F F F F T T T: 找最小值r = mid

代码：

 1class Solution:
 2    def maximumCandies(self, candies: List[int], k: int) -> int:
 3
 4        def check(num):
 5            return sum((c // num) for c in candies) >= k
 6
 7        if sum(candies) < k:
 8            return 0
 9
10        l, r = 1, max(candies)
11        while l < r:
12            mid = (l + r + 1) // 2
13            if check(mid):
14                l = mid
15            else:
16                r = mid - 1
17        return l

复杂度：

时间 O(n · log(max(candies)))
空间 O(1)

3.4 在 D 天内送达包裹的能力 | Medium

题目：包裹按给定顺序装船,每天装的总重不超过载重 load。求 days 天内送完所有包裹的最小载重

思路分析：

二分目标是check(load)：检查以load能否在days内送完，求load最小值
答案分布是：F F F T T T T

踩坑记录：

想清楚上下界：下界不是1，需要装的下最终的那个包裹
包裹必须按顺序，不能调动顺序

代码：

 1class Solution:
 2    def shipWithinDays(self, weights: List[int], days: int) -> int:
 3
 4        def check(load):
 5            s, d = 0, 1
 6            for w in weights:
 7                if s + w > load:
 8                    d += 1
 9                    s = 0
10                s += w
11            return d <= days
12
13        l, r = max(weights), sum(weights)
14        while l < r:
15            mid = (l + r) // 2
16            if check(mid):
17                r = mid
18            else:
19                l = mid + 1
20        return l

复杂度：

时间O(n · log(sum(weights)))
空间O(1)

4 二维数组

4.1 搜索二维矩阵 | Medium

题目：m x n 矩阵,①每行左到右非递减 ②每行第一个 > 前一行最后一个。判断 target 是否存在。要求 O(log(m·n))

思路分析：二维数组左边转换为一维：

1# 一维下标i
2m, n = len(matrix), len(matrix[0])
3row = i // n
4col = i % n

踩坑记录：

注意下标转换是由列数

代码：

 1class Solution:
 2    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
 3        m, n = len(matrix), len(matrix[0])
 4
 5        l, r = 0, m * n - 1
 6        while l < r:
 7            mid = (l + r) // 2
 8            if matrix[mid // n][mid % n] >= target:
 9                r = mid
10            else:
11                l = mid + 1
12        return matrix[l // n][l % n] == target

复杂度：

时间O(log(m·n))
空间O(1)

4.2 搜索二维矩阵 II | Medium

题目：m x n 矩阵,每行左到右升序、每列上到下升序(跨行无保证)。判断 target 是否存在

思路分析：

不能二分，从右上角走z字

踩坑记录：

起点是右上角

代码：

 1class Solution:
 2    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
 3        m, n = len(matrix), len(matrix[0])
 4        i, j = 0, n - 1
 5
 6        while i < m and j >= 0:
 7            if matrix[i][j] == target:
 8                return True
 9            elif matrix[i][j] > target:
10                j -= 1
11            else:
12                i += 1
13        return False

复杂度：

时间O(m + n)(i 只增、j 只减,最多走 m+n 步)
空间O(1)

0 Binary Search Basic#

1 二分模板#

2 旋转数组#

3 构造check函数#

4 二维数组#

0 Binary Search Basic

1 二分模板

2 旋转数组

3 构造check函数

4 二维数组