二分搜索

二分搜索类型

二分的本质不是单调性，而是二分性。意思就是，通过判断中点（可能要结合左右边界）的性质，我可以确定答案在左半段还是右半段。

因为这样的性质，二分有传说中的二分模版和各种边界条件，个人也有这里我觉得可以分两种情况讨论：

1. 二分存在性搜索：在whlie循环中返回答案，循环中l<=r

2. 二分最值搜索：在while循环后返回答案，循环中l<r

3. 边界搜索：在while循环后返回答案，循环中l<=r

看模版中的注释来看细节。在判断区间时，总是用中点m来缩小区间至左边或右边。

参考模版：

存在性搜索

"""
情况一：二分存在性搜索 - 在whlie循环中返回答案
      寻找target

循环：用l<=r 为条件开始搜索，这样如果中点m每次没有找到，
     就可以直接避开m缩小返回。
判断：如果中点符合条件，直接返回。
     如果不在[l,r]左区间则缩小至右区间搜索l=m+1
     否则r=m-1在左区间搜索
退出：如果l和r完美错过，那么没找到
"""

l, r = 0, len(nums)-1
while l<=r:
    m = (+r)>>1
    if nums[m]==n: # 找到了
        return m
    if {...}:      # 判断：如果不在[l, m]闭区间
        l = m+1
    else:
        r = m-1
return -1          # 没找到

最值搜索

"""
情况二：二分最值搜索 - 在while循环后返回答案
      寻找最小/最大值

循环：用l<r 为条件开始搜索
     这样可以保证最值在循环外面返回的时候
     可以返回l或r都一样。
判断：如果不在[l,r]闭合左区间 
     则缩小至右区间搜索l=m+1
     否则r=m在左区间搜索
退出：如果l和r相遇，则达到最值返回l或r都一样
"""

l, r = 0, len(nums)-1
while l<r:
    m = (l+r) >> 1
    if {...}:    # 判断：如果不在[l, m]闭区间
        l = m+1
    else:
        r = m
return nums[l]   # 返回l或者r都一样

边界搜索

"""
情况三：二分边界搜索 - 在while后返回答案
     假设目标仅出现在数组一侧
     找第一次或者最后一次出现

循环：用l<=r为条件开始搜索
     在l和r错过以后返回第一个/最后一个目标值
判断：如果m是可行解
     则根据题意缩小至左或者右区间
退出：如果l和r完美错过
     则返回左边界l，或右边界r
"""

# ✔✔✔✖✖✖中寻找最后一个✔
while l<=r:
    m = (l+r) >> 1
    if possible(m): l = m+1
    else: r = m-1
return r

# ✖✖✖✔✔✔中寻找第一个✔
while l<=r:
    m = (l+r) >> 1
    if possible(m): r = m-1
    else: l = m+1
return l

情况一：存在性查找例题

1. 二分查找(Binary)

2. 搜索旋转排序数组(Rotated I)

3. 搜索旋转排序数组 II(Rotated II)

Binary

def search(nums, target):
    l, r = 0, len(nums)-1
    while l<=r:
        m = (l+r) >> 1
        if nums[m]==target:
            return m
        if target>nums[m]:
            l = m+1
        else:
            r = m-1
    return -1

Rotated I

def search(nums, target):
    l, r = 0, len(nums)-1
    while l<=r:
        m = (l+r) >> 1
        if nums[m]==target: return m
        if nums[l]<=nums[m]: # [l, m] sorted
            if nums[l]<=target<=nums[m]:
                r = m-1
            else:
                l = m+1
        else:
            if nums[m]<=target<=nums[r]:
                l = m+1
            else:
                r = m-1
    return -1

Rotated II

def search(nums, target):
    l, r = 0, len(nums)-1
    while l<=r:
        m = (l+r) >> 1
        if nums[m]==target: return True
        
        # case 0: has duplicate
        if nums[l]==nums[m]==nums[r]:
            l += 1
            r -= 1
        # case 1: [l, m] sorted    
        elif nums[l]<=nums[m]:
            if nums[l]<=target<=nums[m]:
                r = m-1
            else:
                l = m+1
        # case 2: [r, m] sorted
        else:
            if nums[m]<=target<=nums[r]:
                l = m+1
            else:
                r = m-1
    return False

情况二：最值查找例题

1. 寻找峰值(Peak)

2. 寻找旋转排序数组中的最小值(Rotated Min I)

3. 寻找旋转排序数组中的最小值 II(Rotated Min II)

4. 山脉数组中查找目标值(Mountain)

Peak

def findPeakElement(nums):
    l, r = 0, len(nums)-1
    while l<r:
        m = l+(r-l) // 2
        if nums[m+1]>nums[m]:
            l = m+1
        else:
            r = m
    return l

Rotated Min I

def findMin(nums):
    l, r = 0, len(nums)-1
    while l<r:
        m = l+(r-l)//2
        if nums[m] >= nums[r]:
            l = m+1
        else:
            r = m
    return nums[l]

Rotated Min II

def findMin(nums):
    l, r = 0, len(nums)-1
    while l<r:
        m = l+(r-l)//2
        if nums[m]>nums[r]:
            l = m+1
        elif nums[m]<nums[r]:
            r = m
        else:
            r -= 1
    return nums[l]

Mountain

输入：array = [1,2,3,4,5,3,1], target = 3
输出：2
解释：3 在数组中出现了两次，下标分别为 2 和 5，我们返回最小的下标 2。

def findPeak(arr):
    l, r = 0, arr.length()-1
    while l<r:
        m = (l+r) >> 1
        if arr.get(m) < arr.get(m+1):
            l = m+1
        else:
            r = m
    return l

def binarySearch(arr, target, l, r, incr=True):
    while l<=r:
        m = (l+r) >> 1
        val = arr.get(m)
        if val==target:
            return m
        cond = target>val if incr else target<val
        if cond:
            l = m+1
        else:
            r = m-1
    return -1

def findInMountainArray(target, arr):
    peak = self.findPeak(arr)
    res = self.binarySearch(arr, target, 0, peak)
    if res!=-1: return res
    return self.binarySearch(
        arr, target, peak+1,
        arr.length()-1, incr=False)

情况三：边界搜索

极小极大化：本质就是用二分来找找到第一个/最后一个可行解，因为可行解都在答案的一侧。

把可能答案从小到大排列，可以发现可行性的排列大概是✖✖✖✖✔✔✔。我们极小极大化的答案就是第一个✔。而验证答案，即判断是✖还是✔这个过程，很多时候是用贪心来验证的，如果假设答案不可行就返回错误，可行，则判断是可能解再在左区间搜索。

1. 模版：第一个错误的版本(bad)

2. 分享巧克力(chocolate)

3. 在 D 天内送达包裹的能力(package)

4. 爱吃香蕉的珂珂(koko)

5. 分割数组的最大值(split)

6. 制作 m 束花所需的最少天数(flower)

7. 完成所有工作的最短时间 (work)(回溯方法和剪枝：698. 划分为k个相等的子集）

8. H 指数 II (h-index)

bad

left, right = 1, n
while left <= right:
    mid = (left + right) >> 1
    if isBadVersion(mid):
        right = mid - 1
    else:
        left = mid + 1
return left

chocolate

你有一大块巧克力，它由一些甜度不完全相同的小块组成。
我们用数组 sweetness 来表示每一小块的甜度。
你打算和 K 名朋友一起分享这块巧克力，
所以你需要将切割 K 次才能得到 K+1 块，每一块都由一些 连续 的小块组成。

为了表现出你的慷慨，你将会吃掉 总甜度最小 的一块，并将其余几块分给你的朋友们。

请找出一个最佳的切割策略，使得你所分得的巧克力 总甜度最大，并返回这个 最大总甜度。

输入：sweetness = [1,2,3,4,5,6,7,8,9], K = 5
输出：6
解释：你可以把巧克力分成 [1,2,3], [4,5], [6], [7], [8], [9]。

def possible(threshold):
    sweet = k = 0
    for s in sweetness:
        sweet += s
        if sweet >= threshold:
            sweet = 0
            k += 1
        if k > K: return True
    return False

left, right = min(sweetness), sum(sweetness)
while left<=right:
    mid = (left + right) >> 1
    if possible(mid):
        left = mid+1
    else:
        right = mid-1
return right

package

传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。
每一天，我们都会按给出重量的顺序往传送带上装载包裹。
我们装载的重量不会超过船的最大运载重量。

返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5
输出：15
解释：
船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10

请注意，货物必须按照给定的顺序装运，
因此使用载重能力为 14 的船舶并将包装分成
 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。 

def can(mid):
    need, cur = 1, 0
    for weight in weights:
        if cur + weight > mid:
            need += 1
            cur = 0
        cur += weight            
    return need <= D

left, right = max(weights), sum(weights)
while left <= right:
    mid = (left + right) >> 1
    if can(mid):
        right = mid - 1
    else:
        left = mid + 1
return left

koko

珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。
警卫已经离开了，将在 H 小时后回来。

珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。
每个小时，她将会选择一堆香蕉，从中吃掉 K 根。
如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。  

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。

输入: piles = [3,6,7,11], H = 8
输出: 4

def numHours(k): return sum([math.ceil(p/k) for p in piles])
def canFinish(k, h): return numHours(k) <= h

left, right = 1, max(piles)
while left <= right: # look for left bound
    mid = (left+right) >> 1
    if canFinish(mid, h):
        right = mid-1
    else:
        left = mid +1
return left

split

给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。

设计一个算法使得这 m 个子数组各自和的最大值最小。

输入：nums = [7,2,5,10,8], m = 2
输出：18
解释：
一共有四种方法将 nums 分割为 2 个子数组。 
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

def can(val):
    cnt, s = 1, 0
    for n in nums:
        s += n
        if s > val:
            s = n
            cnt += 1
    return cnt > m

left, right = max(nums), sum(nums)
while left<=right:
    mid = (left+right) >> 1
    if can(mid):
        left = mid+1
    else:
        right = mid-1
return left

flower

给你一个整数数组 bloomDay，以及两个整数 m 和 k 。
现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。
花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好 可以用于 一束 花中。

请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。


输入：bloomDay = [1,10,3,10,2], m = 3, k = 1
输出：3
解释：让我们一起观察这三天的花开过程，x 表示花开，而 _ 表示花还未开。
现在需要制作 3 束花，每束只需要 1 朵。
1 天后：[x, _, _, _, _]   // 只能制作 1 束花
2 天后：[x, _, _, _, x]   // 只能制作 2 束花
3 天后：[x, _, x, _, x]   // 可以制作 3 束花，答案为 3

if k*m > len(bloomDay): return -1

def can(days):
    flowers = bouquets = 0
    for d in bloomDay:
        if d > days:
            flowers = 0
            continue
        flowers += 1
        if flowers >= k:
            bouquets += 1
            flowers = 0
            if bouquets==m: return True
    return bouquets == m

left, right = 1, max(bloomDay)
while left<=right:
    mid = (left+right) >> 1
    if can(mid):
        right = mid-1
    else:
        left = mid+1
return left

work

给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。

请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，
且每项工作只能分配给一位工人。
工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。
请你设计一套最佳的工作分配方案，使工人的 最大工作时间 得以 最小化 。

返回分配方案中尽可能 最小 的 最大工作时间 。

输入：jobs = [3,2,3], k = 3
输出：3
解释：给每位工人分配一项工作，最大工作时间是 3 。

def canFinish(nums, groups, target):
    if not nums: return True
    v = nums.pop()
    for i in range(len(groups)):
        if groups[i] + v > target: continue
        groups[i] += v
        if canFinish(nums, groups, target):
            return True
        groups[i] -= v # backtrack job assignment
        if groups[i] == 0: break # PRUNING!
    nums.append(v) # backtrack assigning job
    return False

def can(target):
    nums = sorted(jobs) # PRUNING
    groups = [0 for _ in range(k)]
    return canFinish(nums, groups, target)

left, right = max(jobs), sum(jobs)
while left<=right:
    mid = (left+right) >> 1
    if can(mid):
        right = mid-1
    else:
        left = mid+1
return left

h-index

给定一位研究者论文被引用次数的数组（被引用次数是非负整数），
数组已经按照 升序排列 。编写一个方法，计算出研究者的 h 指数。

h 指数的定义: “h 代表“高引用次数”（high citations），
一名科研人员的 h 指数是指他（她）的 （N 篇论文中）
总共有 h 篇论文分别被引用了至少 h 次。


输入: citations = [0,1,3,5,6]
输出: 3 
解释: 给定数组表示研究者总共有 5 篇论文，
每篇论文相应的被引用了 0, 1, 3, 5, 6 次。
由于研究者有 3 篇论文每篇至少被引用了 3 次，
其余两篇论文每篇被引用不多于 3 次，所以她的 h 指数是 3。

def hIndex(citations: List[int]) -> int:
    n = len(citations)
    l, r = 0, n-1
    while l<=r:
        m = (l+r) >> 1
        if citations[m] >= n-m:
            r = m-1
        else:
            l = m+1
    return n-l

bisect库函数

Python的bisect库让人挺偷懒的，一个具体的例子，在排序数组中查找元素的第一个和最后一个位置，相对对应着bisect的这两个方法：

# 元素target第一个插入点
# 如果在数组的末尾（所有数字都比target小），那么元素不存在
l = bisect.bisect_left(nums, target)

# 元素target的最后插入点
# 如果在数组的开头（所有数字都比target大），那么元素不存在
r = bisect.bisect_right(nums, target)

为了不偷懒，我们分别把这两个方法实现一下。

def bisect_left(nums, target):
    l, r = 0, len(nums)-1
    while l<=r:
        m = (l+r) >> 1
        if nums[m]>=target:
            r = m-1
        else:
            l = m+1
    return l

def bisect_right(nums, target):
    l, r = 0, len(nums)-1
    while l<=r:
        m = (l+r) >> 1
        if target>=nums[m]:
            l = m+1
        else:
            r = m-1
    # 因为bisect_right找的是插入点而非存在点
    # 所以如果target存在，返回它的下一个索引
    return l

例题：在排序数组中查找元素的第一个和最后一个位置

def searchRange(nums, target):
    l = bisect.bisect_left(nums, target)
    r = bisect.bisect_right(nums, target)

    n = len(nums)
    l = l if l!=n and nums[l]==target else -1
    r = r-1 if r and nums[r-1]==target else -1
    return [l, r]