Binary Search

发表于： 分类于：
字数： 1328 阅读：≈ 3分钟

闭区间写法

找该数 

 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 的最小索引。

<, <=, >, >=

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

非单调数组

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

162. 寻找峰值

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

  1. nums[mid]<nums[mid+1]: 峰值在mid+1及其右侧， 因此l=mid+1
  2. 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的距离个数。对应滑动窗口的“越短越合法”。