# 二分搜索

## 二分搜索类型

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

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

1. 二分存在性搜索：在whlie**循环中**返回答案，循环中`l<=r`
2. 二分最值搜索：在while**循环后**返回答案，循环中`l<r`
3. 边界搜索：在while**循环后**返回答案，循环中`l<=r`

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

**参考模版：**

{% tabs %}
{% tab title="存在性搜索" %}
```python
"""
情况一：二分存在性搜索 - 在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          # 没找到
```
{% endtab %}

{% tab title="最值搜索" %}
```python
"""
情况二：二分最值搜索 - 在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都一样
```
{% endtab %}

{% tab title="边界搜索" %}
```python
"""
情况三：二分边界搜索 - 在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
```
{% endtab %}
{% endtabs %}

## 情况一：存在性查找例题

1. [二分查找](https://leetcode-cn.com/problems/binary-search/)(Binary)
2. [搜索旋转排序数组](https://leetcode-cn.com/problems/search-in-rotated-sorted-array/)(Rotated I)
3. [搜索旋转排序数组 II](https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/)(Rotated II)

{% tabs %}
{% tab title="Binary" %}
```python
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
```
{% endtab %}

{% tab title="Rotated I" %}
```python
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
```
{% endtab %}

{% tab title="Rotated II" %}
```python
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
```
{% endtab %}
{% endtabs %}

## 情况二：最值查找例题

1. [寻找峰值](https://leetcode-cn.com/problems/find-peak-element/)(Peak)
2. [寻找旋转排序数组中的最小值](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/)(Rotated Min I)
3. [寻找旋转排序数组中的最小值 II](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/)(Rotated Min II)
4. [山脉数组中查找目标值](https://leetcode-cn.com/problems/find-in-mountain-array/)(Mountain)

{% tabs %}
{% tab title="Peak" %}
```python
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
```
{% endtab %}

{% tab title="Rotated Min I" %}
```python
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]
```
{% endtab %}

{% tab title="Rotated Min II" %}
```python
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]
```
{% endtab %}

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

```python
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)
```
{% endtab %}
{% endtabs %}

## 情况三：边界搜索

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

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

1. 模版：[第一个错误的版本](https://leetcode-cn.com/problems/first-bad-version/)(bad)
2. [分享巧克力](https://leetcode-cn.com/problems/divide-chocolate/)(chocolate)
3. [在 D 天内送达包裹的能力](https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/)(package)
4. [爱吃香蕉的珂珂](https://leetcode-cn.com/problems/koko-eating-bananas/)(koko)
5. [分割数组的最大值](https://leetcode-cn.com/problems/split-array-largest-sum/)(split)
6. [制作 m 束花所需的最少天数](https://leetcode-cn.com/problems/minimum-number-of-days-to-make-m-bouquets/)(flower)
7. [完成所有工作的最短时间](https://leetcode-cn.com/problems/find-minimum-time-to-finish-all-jobs/) (work)(回溯方法和剪枝：[698. 划分为k个相等的子集](https://leetcode-cn.com/problems/partition-to-k-equal-sum-subsets/)）
8. [H 指数 II](https://leetcode-cn.com/problems/h-index-ii/) (h-index)

{% tabs %}
{% tab title="bad" %}
```python
left, right = 1, n
while left <= right:
    mid = (left + right) >> 1
    if isBadVersion(mid):
        right = mid - 1
    else:
        left = mid + 1
return left
```
{% endtab %}

{% tab title="chocolate" %}
```python
你有一大块巧克力，它由一些甜度不完全相同的小块组成。
我们用数组 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]。
```

```python
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
```
{% endtab %}

{% tab title="package" %}
```python
传送带上的包裹必须在 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) 是不允许的。 
```

```python
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
```
{% endtab %}

{% tab title="koko" %}
```python
珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。
警卫已经离开了，将在 H 小时后回来。

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

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

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

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

```python
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
```
{% endtab %}

{% tab title="split" %}
```python
给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。

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

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

```python
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
```
{% endtab %}

{% tab title="flower" %}
```python
给你一个整数数组 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
```

```python
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
```
{% endtab %}

{% tab title="work" %}
```python
给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。

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

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

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

```python
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
```
{% endtab %}

{% tab title="h-index" %}
```python
给定一位研究者论文被引用次数的数组（被引用次数是非负整数），
数组已经按照 升序排列 。编写一个方法，计算出研究者的 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。
```

```python
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
```
{% endtab %}
{% endtabs %}

## bisect库函数

Python的[bisect](https://docs.python.org/3/library/bisect.html)库让人挺偷懒的，一个具体的例子，在排序数组中查找元素的第一个和最后一个位置，相对对应着bisect的这两个方法：

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

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

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

```python
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
```

### **例题：**[**在排序数组中查找元素的第一个和最后一个位置**](https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/)

```python
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]
```
