Binary Search

March 13, 2025

https://leetcode.cn/discuss/post/3579164/ti-dan-er-fen-suan-fa-er-fen-da-an-zui-x-3rqn/

闭区间写法

找该数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    # 标准的二分搜索框架，搜索目标元素的索引，若不存在则返回 -1
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
        return -1

找左边界

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def search(self, nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            right=mid-1
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
    return left

左闭右开

找左边界

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def left_bound(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums)
    
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            right = mid
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid

    return left

如果 target 不存在，搜索左侧边界的二分搜索返回的索引是大于 target 的最小索引。

为什么？因为l-1及其左边肯定不是答案，r及其右边肯定是答案，循环结束时，l==r,返回l则代表这是“满足条件的最小索引”

<, <=, >, >=

“>=“即为寻找某数的左侧边界
“>“可看作寻找x+1的左侧边界
“<=“看做寻找x+1的左侧边界-1，或者找x 的右侧边界-1 “<“看做寻找x的左侧边界-1

bisect_left找的是第一个大于等于该数的index
bisect_right返回第一个 a[j] > x 的位置，如果存在多个相等元素，返回这些相等元素右边的位置。

非单调数组

红色（l-1及其左边）代表目标左边，蓝色（r及其右边）代表目标及其右边，也就是说nums[n-1]初始为蓝色。

162. 寻找峰值

每次拿nums[mid]和 nums[mid+1]比较。以左闭右开写法举例：

nums[mid]<nums[mid+1]: 峰值在mid+1及其右侧，因此l=mid+1
nums[mid]>nums[mid+1]: 峰值为mid及其左侧区域, r=mid

注意这题需要初始 r=len(nums)-1，不然 nums[mid+1]会溢出。但即使如此，num[n-1]也不会在答案中被漏掉，这是因为循环结束时，l==r, 会返回。如[1,2,3,4].

左闭右开写法: r及其右边可能是答案，l-1及其左边不是答案

1901. 寻找峰值 II

灵神图解

要求时间复杂度为O(NlogM)，因此只需要对行进行二分。
先找行，nums[mid]这行里面最大的元素X，拿它和它下面的元素A比较。
如果小于，则从A出发，一定存在一条单调递增直到峰值的路径，并且不会走到mid那一行，因为 mid那一行最大的都比A小了。
所以就在下面那几排找峰值即可。

如果大于，要么X就是峰顶，要么X往上走，存在一条走到峰顶的路

153. 寻找旋转排序数组中的最小值

将nums[mid]与nums[n-1]比较。

单调数组

4. 寻找两个正序数组的中位

可视为划分数组，在两个数组中找出一条分割线，分割线左边的元素个数为(m+n+1)/2，分割线左边最大的数<分割线右边最小的数
如果总共有奇数个元素，那么答案为分割线左边最大的数
如果总共有偶数个元素，那么答案为分割线左边最大的数与分割线右边最小的数的平均值。

Alt text

把第一个数组的每个数字间隙视为可枚举的对象，二分搜索合适的间隙。总共有m+1个间隙。
为了防止索引越界，令长度短的数组为第一个数组。

目标分割线满足：nums1[i-1]<nums2[j] and nums1[i]>nums2[j-1],j=(m+n+1)//2-i

类似题目：295. 数据流的中位数

用堆实现，分左边堆和右边堆。左边堆的数量可以比右边多一个。

最小化最大值

410. 分割数组的最大值.

遍历数组，当前累加和大于mid时，创建一个新的分割，cnt+=1.

当 cnt==k时，返回 False。

K 小/大

第 k 小等价于：求最小的 x，满足 ≤x 的数至少有 k 个。

719. 找出第 K 小的数对距离

辅助函数：数一下所有距离中，小于等于X的距离个数。对应滑动窗口的“越短越合法”。

378. 有序矩阵中第 K 小的元素

第 K 小的元素=最小的x,使得矩阵中最少有K个元素小于等于它

cntLessEqual(x)在矩阵中搜索，返回小于等于x的元素的个数。性质：在矩阵中，任意取一个元素，小于等于它的元素正好在矩阵的左上方

因此从左下角开始搜索，若当前元素num小于等于x，则往右移动，同时可知num即其上方所有元素皆小于x，故res+=i+1

为什么二分查找的结果一定在矩阵里？

假设y是最小的元素，使得有k个元素小于等于y,而y不在矩阵中
x是矩阵中第一个大于y的元素，则有k个元素小于等于x（因为y不在矩阵中）。这与第一句话相互矛盾。

也可以这样理解：答案一定位于[left, right)中，在循环的最后，区间被缩小到里面只有一个元素，那么它一定是答案

其它

1539. 第 k 个缺失的正整数

用一个数组miss记录到i为止一共缺失了几个整数，然后用bisect+分类讨论。

miss[i]=arr[i]-1-i

300. 最长递增子序列

g[i]表示所有长度为i+1的子序列中，有可能的最小的最后一个数字。
遍历原始数组，每遇到一个新数字，看他是否比现在g的最后一个数字要大，如果要大，就加在g数组的末尾；如果不是，就让它插入到g中应该的位置，替代以前的元素。