bisect

目标: 掌握二分查找的思想和变种
学习内容:
1. 标准二分查找
2. 二分查找的变种（如查找左边界、右边界）, 二分查找变形问题
3. 二分查找的应用: 有序数组查找, 最优解的范围搜索, 查找边界, 旋转数组查找
推荐题目:
- LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置
- LeetCode 35. 搜索插入位置
- LeetCode 704. 二分查找
- LeetCode 69. x 的平方根 (二分查找)
- LeetCode 153. 寻找旋转排序数组中的最小值 (二分查找)
- LeetCode 33. 搜索旋转排序数组 (二分查找)
- LeetCode 4. 寻找两个正序数组的中位数 (二分查找)

python 自带的二分查找库

def bisect(
    a, # 给定一个升序数组
    x, # 目标值
    lo:int=0,
    hi:int | None = None
  ): # 返回第一个大于目标值的索引 在 a[lo:hi] 里
  ...
# 时间复杂度: O(logn)
from bisect import bisect

a = [1,9,9,9,200,500]
print(bisect(a, 3)) # 1，a[1] = 9
print(bisect(a, 9)) # 4，a[4] = 200
print(bisect(a, -1)) # 0，a[0] = 1
print(bisect(a, 1000)) # 6，a[6]: error

a.reverse() # [500, 200, 9, 9, 9, 1]
# 找到第一个小于 x 的索引
a_rev_ = [-i for i in a] # [-500, -200, -9, -9, -9, -1]
print(bisect(a_rev_, -3)) # 5，a_[5] = -1
print(bisect(a_rev_, -9)) # 5，a_[5] = -1
print(bisect(a_rev_, -1)) # 6，a_[6]: err
print(bisect(a_rev_, -1000)) # 0，a_[0] = -500

例题

洛谷 P2249 【深基13.例1】查找

题目描述

输入个不超过的单调不减的（就是后面的数字不小于前面的数字）非负整数，然后进行次询问。对于每次询问，给出一个整数，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出。

输入格式

第一行个整数和，表示数字个数和询问次数。

第二行个整数，表示这些待查询的数字。

第三行个整数，表示询问这些数字的编号，从开始编号。

输出格式

输出一行，个整数，以空格隔开，表示答案。

输入输出样例

输入

11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6

输出

1 2 -1

说明/提示

数据保证，，，

本题输入输出量较大，请使用较快的 IO 方式。

题解

获得输入

import sys
input = lambda: sys.stdin.readline().strip()
n, m = map(int, input().split())
a_ls = list(map(int, input().split()))
q_ls = list(map(int, input().split()))

方法一: 二分查找

from bisect import bisect
from typing import List
def m1(n:int, m:int, a_ls:List[int], q_ls:List[int]) -> List[int]:
  s = set(a_ls)
  res = []
  for q in q_ls:
    if q in s:
      res.append(bisect(a_ls, q-1)+1)# + 1是因为题目的输出是从1开始编号
    else:
      res.append(-1)
  return res
print(*m1(n, m, a_ls, q_ls))

实战题:2563

LeetCode 2563. 统计公平对数目

给你一个下标从 0 开始、长度为 n 的整数数组 nums 和两个整数 lower 和 upper, 返回公平数对的数目。如果 (i, j) 满足以下情况, 则认为它是一个公平数对:

0 <= i < j < n且
lower <= nums[i] + nums[j] <= upper 示例 1:

输入: nums = [0,1,7,4,4,5], lower = 3, upper = 6 输出: 6 解释: 共计 6 个公平数对: (0,3), (0,4), (0,5), (1,3), (1,4), (1,5)。 示例 2: 输入: nums = [1,7,9,2,5], lower = 11, upper = 11 输出: 1 解释: 共计 1 个公平数对: (2,3)。 提示:

1 <= nums.length <= 10^5
nums.length == n
-10^9 <= nums[i] <= 10^9
-10^9 <= lower <= upper <= 10^9

方法一: 枚举

def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
  res = 0
  for i in range(len(nums)):
    for j in range(i+1, len(nums)):
      if lower <= nums[i] + nums[j] <= upper:
        res += 1
  return res

方法二: 二分查找

注意到排序不影响结果(总数)
对 lower <= nums[i] + nums[j] <= upper 进行变形，得到 lower - nums[i] <= nums[j] <= upper - nums[i]，
即对于每个 i，找到 nums[j] 在 [lower - nums[i], upper - nums[i]] 之间的个数。
j 的范围是 [i+1, n)，所以可以对 nums 进行排序，然后对于每个 i, 在 j的范围中，找到 lower - nums[i] 和 upper - nums[i] 的位置，然后计算这两个位置之间的个数。

from bisect import bisect

def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
  res = 0
  nums.sort()
  for i in range(len(nums)):
    L = bisect(nums, lower - nums[i]-1, i+1)
    R = bisect(nums, upper - nums[i], i+1)-1
    res += R - L + 1 # 索引做差+1 得到之间的个数, 对于前后都是闭区间
  return res

自己实现二分查找

python3.12 给 bisect 增加了参数 key: func, 但是 python3.8 只有4个参数: a, x, lo=0, hi=None,

因此需要学会自己实现二分查找, 以应对更多的情况

实现思路:

对于区间 [lo, hi), 划分为 [lo, mid) 和 [mid, hi), mid = (lo + hi) >> 1{:py}
if x < a[mid]: hi = mid{:py}, else: lo = mid+1{:py}
重复步骤1,2 直到 lo == hi

def bisect(a, x, lo=0, hi=None, key=lambda f: f):
  if hi is None: hi = len(a)
  while lo < hi:
    mid = (lo + hi) >> 1
    if x < key(a[mid]): hi = mid # 补上未来版本的 key
    else: lo = mid + 1
  return lo

leetCode 2226

LeetCode 2226. 每个小孩最多能分到多少糖果

给你一个 下标从 0 开始 的整数数组 candies 。数组中的每个元素表示大小为 candies[i] 的一堆糖果。你可以将每堆糖果分成任意数量的子堆，但无法再将两堆合并到一起。

另给你一个整数 k 。你需要将这些糖果分配给 k 个小孩，使每个小孩分到相同数量的糖果。每个小孩可以拿走 至多一堆 糖果，有些糖果可能会不被分配。

返回每个小孩可以拿走的 最大糖果数目 。

示例 1:

输入: candies = [5,8,6], k = 3 输出: 5 解释: 可以将 candies[1] 分成大小分别为 5 和 3 的两堆，然后把 candies[2] 分成大小分别为 5 和 1 的两堆。现在就有五堆大小分别为 5、5、3、5 和 1 的糖果。可以把 3 堆大小为 5 的糖果分给 3 个小孩。可以证明无法让每个小孩得到超过 5 颗糖果。 示例 2: 输入: candies = [2,5], k = 11 输出: 0 解释: 总共有 11 个小孩，但只有 7 颗糖果，但如果要分配糖果的话，必须保证每个小孩至少能得到 1 颗糖果。因此，最后每个小孩都没有得到糖果，答案是 0 。 示例 3:

1 <= candies.length <= 10^5
1 <= candies[i] <= 10^7
1 <= k <= 10^12

题解:

# 可知问题解一定在 [0, max(candies)] 之间
# 答案就是寻找有多个 能被 res 整除的数 在[0, max(candies)] 之间
# def bisect(x,lo=0,hi=None,key=lambda f: f):
# #   if hi is None: hi = len(a)
#   while lo < hi:
#     mid = (lo + hi) >> 1
#     if x > key(mid): hi = mid
#     else: lo = mid + 1
#   return lo

class Solution:
    def maximumCandies(self, candies: List[int], k: int) -> int:
        tot = sum(candies)
        r = tot//k
        if r==1: return 1
        elif tot<k: return 0
        lo = 1
        hi = 10**12+10
        key = lambda x: sum([i//x for i in candies])
        while lo < hi:
            mid = (lo + hi) >> 1
            if k > key(mid): hi = mid
            else: lo = mid + 1
        return lo - 1
        # res = bisect(k, lo=1, hi=max(candies)+1, key=)
        # return res -1

lanqiao 3.冶炼金属

https://www.lanqiao.cn/problems/3510/learning/?page=1&first_category_id=1&second_category_id=3&tags=%E4%BA%8C%E5%88%86,%E7%9C%81%E8%B5%9B&tag_relation=intersection&difficulty=20

小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 V，V 是一个正整数，这意味着消耗 V 个普通金属 O 恰好可以冶炼出一个特殊金属 X，当普通金属 O 的数目不足 V 时，无法继续冶炼。

现在给出了 N 条冶炼记录，每条记录中包含两个整数 A 和 B，这表示本次投入了 A 个普通金属 O，最终冶炼出了 B 个特殊金属 X。每条记录都是独立的，这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。

根据这 N 条冶炼记录，请你推测出转换率 V 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。

基础

排序数组中查找元素的first和last位置

LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums, 和一个目标值 target. 请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target, 返回 [-1, -1]

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

示例 3:

输入: nums = [], target = 0
输出: [-1,-1]

提示:

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums 是一个非递减数组
-10^9 <= target <= 10^9

def bisect(a, x, lo=0, hi=None):
    if hi is None: hi = len(a)
    while lo < hi:
        mid = (lo + hi) >> 1
        if x < a[mid]: hi = mid
        else: lo = mid + 1
    return lo
def searchRange(self, nums: List[int], target: int) -> List[int]:
    if not nums: return [-1, -1]
    l = bisect(nums, target-1)
    r = bisect(nums, target)
    if l == r: return [-1, -1]
    return [l, r-1]

搜索插入位置

LeetCode 35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 为 无重复元素 的升序排列数组
-10^4 <= target <= 10^4

from bisect import bisect
def searchInsert(self, nums: List[int], target: int) -> int:
    right = bisect(nums, target)
    if target == nums[right-1]:
        return right - 1
    else:
        return right

二分查找

LeetCode 704. 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target, 如果目标值存在返回下标，否则返回 -1

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4 解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1 解释: 2 不存在 nums 中因此返回 -1

提示:

你可以假设 nums 中的所有元素是不重复的
n 将在 [1, 10000] 之间
nums 的每个元素都将在 [-9999, 9999]之间