Algorithm | 二分探索をPython3で解説（例題あり）

## 二分探索とは

　二分探索（バイナリサーチ）とは、かんたんにいうと、数字がソートされたリストのなかから、求めたい数を効率的に求めるための手法である。

　例えば、次のようなリストがあったとしよう。

```python
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
```

　このとき、このリストから`7`を求めたいとする。
　通常は、`0`から前から順番に見ていって探し出す、という手法をとる。このとき、`0, 1, 2,...`とみてくので、探すまでに8回の操作が必要である。
　
　しかし、これを二分探索をもちいることでより効率的に値を探し出すことができる。
　二分探索は、まず真ん中の値から探索を開始する。このリストであれば、リストの最小値である`0`と最大値である`9`を足して2で割った数を真ん中の値`mid`とする。つまり、`4`の値が取れる。ここで、求めたい値である`7`がこの値よりも大きいかどうかを判定する。大きければ`left`に値を入れ、小さければ`right`に値を代入する。この操作で1回分である。このときは、`7`は`4`よりも大きいので、`left`に`4`を代入する。

　これを`left`が`right`の値を超える（そもそもリストに値が存在しない）、もしくは、`mid`の値が見つかるまで、続ける。

　続きを見ていこう。今、`left == 4, right == 9`となっているので、これらを足して2で割った値、つまり、`mid == 6`となる。このとき、`7`は`6`よりも大きいので、`left = 6`とする。これで2回目の操作である。

　`left == 6, right == 9`なので、`mid == 7`を追加する。このとき`mid == 7`で値が見つかったので、この値を返す。

　このようにすると、はじめの操作では8回かかっていたのに比べて、3回の操作で目的の値を探し出すことができる。たった5回かと思うが、リストが長くなるほど、効果を発揮する。通常の全探索では、計算量$O(N)$かかるが、二分探索は$O(logN)$で目的の値を探し出すことができる。

## どうやって実装するか

　二分探索には、大きく分けて3つの手法があると考えている。
　**ライブラリを使う**、**めぐる式二分探索を使う**、**自分で実装する**の3つである。

### 手法1: ライブラリ(import bisect)

　Python3には、二分探索をするために便利なライブラリが存在する。これが`bisect`だ。

　これを用いることで、コードを書かなくてもかんたんな二分探索なら実装できる。
　ライブラリの`bisect`は、大きく分けて2つの操作ができる。`bisect(_left, _right)`と`insort`である。

#### bisect_right, bisect_left

　まず、`bisect_right, bisect_left`について説明する。これは、`bisect_right(リスト, 目的の数)`と書き、リストから目的の値が入るインデックスを返してくれるというものである。`bisect_right`と`bisect_left`の2つあるのは、重複した値に対する操作である。以下のようなコードでは、同じ値がある場合、それぞれの端の値を返すようになっている。

```python
from bisect import bisect_right, bisect_left

numbers = [0, 1, 2, 3, 4, 5, 6, 7, 7, 8, 9]

print(bisect_left(numbers, 7))
print(bisect_right(numbers, 7))
```

```python
# output
>> 7
>> 9
```

#### insort

　次に、`insort`について説明する。これは、`insort(リスト、挿入したい値)`と書き、リストの順序を崩さずに、値を挿入することができる。例えば、次のようにだ。

```python
from bisect import insort

numbers = [0, 1, 3, 4, 5, 6, 8, 9]

insort(numbers, 2)
print(numbers)

insort(numbers, 7)
print(numbers)
```

```python
# output
>> [0, 1, 2, 3, 4, 5, 6, 8, 9]
>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
```

その他メソッドはこちらの公式ドキュメントに記載されている。

https://docs.python.org/ja/3/library/bisect.html

### 手法2: めぐる式二分探索

https://qiita.com/drken/items/97e37dd6143e33a64c8c

めぐる式二分探索とは、次のようなコードの二分探索のことをいう。

```python
def is_ok(arg):
    # 条件を満たすかどうか？問題ごとに定義
    pass


def meguru_bisect(ng, ok):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok
```

　これに、問題文に応じて条件を設定してあげると、`AC`することができる。

　めぐる式二分探索のメリットは以下の通りである。

- 定式化されている
- 実行してもバグりにくい
- リストではなくても、二分探索できる
- 二分探索ということが見抜ければ、あとは条件を考えてあげるだけで良い

### 手法3: 自分で実装

　3つ目は、自分で実装する方法である。参考までに、一般的な二分探索のコードを以下に書き記しておく。

#### whileで実装

```python
def binary_search(numbers, value):
    left, right = 0, len(numbers) - 1
    while left <= right:
        mid = (left + right) // 2
        if numbers[mid] == value:
            return mid
        elif numbers[mid] < value:
            left = mid + 1
        else:
            right = mid - 1
    return -1
```

#### recursible（再帰関数）で実装

```python
def binary_search(numbers, value):
    def _binary_search(numbers, value, left, right):
        if left > right:
            return -1
        
        mid = (left + right) // 2
        if numbers[mid] == value:
            return mid
        elif numbers[mid] < value:
            return _binary_search(numbers, value, mid + 1, right)
        else:
            return _binary_search(numbers, value, left, mid - 1)
    return _binary_search(numbers, value, 0, len(numbers) - 1)
```

## 二分探索を見分けるポイント

　二分探索の手法について述べてきたが、これをどうやって見分ければよいのか。大きく分けて以下の2つがあると考えている。

- 制約が異常に大きい
    - ex) $1 \leq A \leq 10^9$, $1 \leq X \leq 10^{18}$ 
- 「次の制約を満たす、最大or最小の数を求めてください」

　問題文にこれらの文章が入っていれば、二分探索である可能性が高い。

## 二分探索の解き方

- 数直線を考えて、境界線がどこかを調べる
- 条件式を立式する
- 何を二分探索で求めたいのかを明確にする

　この3つを考えることができれば、二分探索で問題を解くことができる。

　次からは、各手法の例題をみていこう。answerの下に回答があるので、見たくない方は途中で止めていただけると幸いだ。

## 0- 二分探索の基本問題

### 例題0: AOJ ALDS1 Search II

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_4_B

#### answer

```python
def binary_search(numbers, value):
    left, right = 0, len(numbers) - 1
    while left <= right:
        mid = (left + right) // 2
        if numbers[mid] == value:
            return mid
        elif numbers[mid] < value:
            left = mid + 1
        else:
            right = mid - 1
    return -1


n = int(input())
slist = list(map(int, input().split()))
q = int(input())
tlist = list(map(int, input().split()))
cnt = 0

for t in tlist:
    if binary_search(slist, t) != -1:
        cnt += 1

print(cnt)
```


## 1- `import bisect`を用いた例題

### 例題1-1: ABC030 C - 飛行機乗り

https://atcoder.jp/contests/abc030/tasks/abc030_c

#### answer

```python

def main():
    from bisect import bisect_left

    n, m = map(int, input().split())
    x, y = map(int, input().split())
    alist = list(map(int, input().split()))
    blist = list(map(int, input().split()))

    now_idx = 0
    cnt = 0

    while True:
        now = alist[now_idx] + x
        now_idx = bisect_left(blist, now) # blistの時刻からnowを超えないblistのインデックス番号を返す

        if now_idx == len(blist):
            print(cnt)
            break

        now = blist[now_idx] + y
        now_idx = bisect_left(alist, now) # alistの時刻からnowを超えないalistのインデックス番号を返す

        if now_idx == len(alist):
            cnt += 1
            print(cnt)
            break

        cnt += 1


if __name__ == '__main__':
    main()
```


### 例題1-2: ABC061 C - Big Array

https://atcoder.jp/contests/abc061/tasks/abc061_c

#### answer

```python
def main():
    from itertools import accumulate
    import bisect

    n, k = map(int, input().split())
    numbers = [0]*(10**5+1)

    for i in range(n):
        a, b = map(int, input().split())
        numbers[a] += b # 各数字が何個追加されるかを数える

    sum_numbers = list(accumulate(numbers)) # 累積和

    ans = bisect.bisect_left(sum_numbers, k) # k以上となる累積和を探す
    print(ans)


if __name__ == '__main__':
    main()
```

### 例題1-3: ABC077 C - Snuke Festival 

https://atcoder.jp/contests/abc077/tasks

#### answer

```python
def main():
    import bisect

    n = int(input())
    alist = list(map(int, input().split()))
    blist = list(map(int, input().split()))
    clist = list(map(int, input().split()))

    sort_alist = sorted(alist)
    sort_clist = sorted(clist)

    cnt = 0

    for b in blist:
        low = bisect.bisect_left(sort_alist, b) # 昇順のalistからbがはいるインデックスを返す
        high = bisect.bisect_right(sort_clist, b)# 昇順のclistからbがはいるインデックスを返す
        cnt += low *(n - high) # bよりも下、bよりも上の数を数えてカウント

    print(cnt)


if __name__ == '__main__':
    main()
```

### 例題1-4: ABC113 C - ID

https://atcoder.jp/contests/abc113/tasks/abc113_c

#### answer

```python
def main():
    from bisect import bisect_left

    n, m = map(int, input().split())

    city = [[] for _ in range(n+1)]

    plist = []
    ylist = []

    for i in range(m):
        p, y = map(int, input().split())
        plist.append(p)
        ylist.append(y)
        city[p].append(y)

    for i in range(n+1):
        city[i].sort()

    for i in range(m):
        print(str(plist[i]).zfill(6) +
            (str(bisect_left(city[plist[i]], ylist[i])+1)).zfill(6))

if __name__ == '__main__':
    main()
```

### 例題1-5: ABC172 C - Tsundoku 

https://atcoder.jp/contests/abc172/tasks/abc172_c

#### answer

```python
def main():
    from itertools import accumulate
    import bisect

    n, m, k = map(int, input().split())
    alist = [0]+list(map(int, input().split()))
    blist = list(map(int, input().split()))

    acc_alist = list(accumulate(alist))
    acc_blist = list(accumulate(blist))

    ans = 0

    # NlogN
    for i in range(n+1): # Aの累積和を順番に
        a = acc_alist[i]
        check = k - a # Bの本を読む時間

        if check < 0: # 読む時間がなければループを抜ける
            break

        ans = max(bisect.bisect_right(acc_blist, check)+i, ans) # Bの本を読む時間がBの本を読む時間にかかる累積和のリストのどこにあてはまるかを二分探索し、インデックス番号を返す

    print(ans)


if __name__ == '__main__':
    main()
```

### 例題1-6: ABC119 D - Lazy Faith

https://atcoder.jp/contests/abc119/tasks/abc119_d

#### answer

```python
def main():
    import bisect

    a, b, q = map(int, input().split())

    INF = 10**18

    slist = [-INF] + list(int(input()) for _ in range(a)) + [INF]
    tlist = [-INF] + list(int(input()) for _ in range(b)) + [INF]

    for i in range(q):
        x = int(input())

        b, d = bisect.bisect_right(slist, x), bisect.bisect_right(tlist, x)
        res = INF

        for s in [slist[b-1], slist[b]]: # xのslist左右
            for t in [tlist[d-1], tlist[d]]: # xのtlist左右
                d1, d2 = abs(s-x) + abs(t-s), abs(t-x) + abs(s-t) # sが近いとき, tが近いとき
                res = min(res, d1, d2) # 最小の移動距離を保存

        print(res)


if __name__ == '__main__':
    main()
```


### 例題1-7: ABC143 D - Triangles

https://atcoder.jp/contests/abc143/tasks/abc143_d

#### answer

```python
def main():
    from bisect import bisect_right

    n = int(input())
    llist = list(map(int, input().split()))
    sort_llist = sorted(llist)

    ans = 0
    for i in range(2, n):  # 一番長い辺
        for j in range(1, i):  # 2番目に長い辺
            ans += max(0, j - bisect_right(sort_llist,
                                           sort_llist[i]-sort_llist[j])) # 一番短い辺を二分探索する

    print(ans)


if __name__ == '__main__':
    main()
```

### 例題1-8: ABC217 D - Cutting Woods

https://atcoder.jp/contests/abc217/tasks/abc217_d

#### answer

```python
def main():
    from bisect import bisect_left, insort
    from array import array

    l, q = map(int, input().split())

    wood = array('i', [0, l]) # listでは間に合わないのでarray

    for i in range(q):
        c, x = map(int, input().split())
        if c == 1:
            insort(wood, x) # リストの順序を崩さず値を挿入
        elif c == 2:
            idx = bisect_left(wood, x) # xがリストに位置するインデックスを返す
            print(wood[idx]-wood[idx-1]) # 両端の値の差が答え

if __name__ == '__main__':
    main()
```

### 例題1-9: ARC037 C - 億マス計算

https://atcoder.jp/contests/arc037/tasks/arc037_c

#### answer

```python
def main():
    from bisect import bisect_right

    def is_ok(x):
        cnt = 0
        for a in alist:
            a = x // a # a_i * b_j <= Xの判定
            cnt += bisect_right(blist, a)
        return cnt >= k # k番目以上なら

    def meguru_bisect(ng, ok): # めぐる式二分探索
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok

    n, k = map(int, input().split())
    alist = list(map(int, input().split()))
    blist = list(map(int, input().split()))

    alist.sort()
    blist.sort()

    print(meguru_bisect(-1, 10 ** 18 + 1))


if __name__ == '__main__':
    main()
```

### 例題1-10: ABC231 C - Counting 2

https://atcoder.jp/contests/abc231/tasks/abc231_c

#### answer

```python
# bisect
def main():
    from bisect import bisect_left

    n, q = map(int, input().split())
    alist = list(map(int, input().split()))
    sort_alist = sorted(alist)

    for _ in range(q):
        x = int(input())
        ans = n - bisect_left(sort_alist, x)
        print(ans)

if __name__ == '__main__':
    main()
```

## 2- めぐる式二分探索を用いた例題

### 例題2-1: ABC023 D - 射撃王

https://atcoder.jp/contests/abc023/tasks/abc023_d

#### answer

```python
def main():
    def is_ok(x):
        limit = []

        for i in range(n):
            limit.append((x-hlist[i])//slist[i]) # x-hlist[i]は現在の高さ、slist[i]でわると、いつまでに割らないといけないかがわかる
        
        limit.sort()

        for i in range(n): # limitのi番目の時刻が時刻i以内になっているか
            if limit[i] < i: # 割らないといけない時刻までに、iが来てしまったらアウト
                return False
        return True

    def meguru_bisect(ng, ok):
        while abs(ok - ng) > 1: # okとngの時刻さが1または0になったらループを抜ける
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid # okの時刻より下
            else:
                ng = mid # ngの時刻より上
        return ok

    n = int(input())
    hlist = []
    slist = []

    for i in range(n):
        h, s = map(int, input().split())
        hlist.append(h)
        slist.append(s)

    print(meguru_bisect(0, int(1e+14))) # H,Sの最大値1,000,000,000に注意


if __name__ == '__main__':
    main()
```

### 例題2-2: ABC034 D - 食塩水

https://atcoder.jp/contests/abc034/tasks/abc034_d

#### answer

```python
def main():
    def is_ok(wj):
        wplist = []

        for i in range(n):
            wplist.append(wlist[i]*(plist[i]-wj)/100.0)

        wplist.sort(reverse=True)

        total = sum(wplist[:k])
        return total >= 0

    def meguru_bisect(ng, ok):
        while (abs(ok - ng) > 1e-10):
            mid = (ok + ng) / 2.0
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok

    n, k = map(int, input().split())
    wlist = []
    plist = []

    for _ in range(n):
        w, p = map(int, input().split())
        wlist.append(w)
        plist.append(p)

    ng = 100
    ok = 0.0

    print(f'{meguru_bisect(ng, ok)}')


if __name__ == '__main__':
    main()

```

### 例題2-3: ABC063 D - Widespread

https://atcoder.jp/contests/abc063/tasks/arc075_b

#### answer

```python
def main():
    def is_ok(x):
        c = 0
        for i in range(n):
            monster = monsters[i] - x * b # monsters全体にbがx回分のダメージ

            if monster <= 0: # monsterが倒せているかどうか
                continue

            c += monster // a_b # 残りHPに対してa-bのダメージを

            if monster % a_b: # a-bのダメージでHPがまだ残っていたらもう1回分
                c += 1

        return c <= x # a-bの攻撃回数がbの攻撃回数以下であればTrue

    def meguru_bisect(ng, ok): # 二分探索
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok

    n, a, b = map(int, input().split())
    a_b = a - b

    monsters = list(int(input()) for _ in range(n))

    ng, ok = 0, 1010101010

    print(meguru_bisect(ng, ok))


if __name__ == '__main__':
    main()
```

### 例題2-4: ARC050 B - 花束

https://atcoder.jp/contests/arc050/tasks/arc050_b

#### answer

```python
def main():
    def is_ok(k):
        if r-k < 0 or b-k < 0: # 各色の花は必ず一本は必要なので、それがどこまで絞れるか確認する
            return False
        return ((r-k)//(x-1))+((b-k)//(y-1)) >= k # 各色に一本ずつ使えることが確認できたら、余っている花に対して、花束の数を数える

    def meguru_bisect(ng, ok):
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok

    r, b = map(int, input().split())
    x, y = map(int, input().split())

    print(meguru_bisect(10**18+1, 0))


if __name__ == '__main__':
    main()
```

### 例題2-5: ABC174 E - logs

https://atcoder.jp/contests/abc174/tasks/abc174_e

#### answer

```python
def main():  # 最大値の最小化
    def is_ok(x):
        now = 0
        for i in range(n):
            now += (alist[i]-1)//x # それぞれの丸太を何回切ればよいかをカウント
        return now <= k # 切った回数がk以下であれば

    def meguru_bisect(ng, ok):
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok

    n, k = map(int, input().split())
    alist = list(map(int, input().split()))

    ng, ok = 0, 10**9+1

    print(meguru_bisect(ng, ok))


if __name__ == '__main__':
    main()
```

### 例題2-6: ABC216 E - Amusement Park

https://atcoder.jp/contests/abc216/tasks/abc216_e

#### answer

```python
def main():

    def is_ok(x):
        now = 0
        for i in range(n):
            if alist[i] >= x: # A_iがx以上の数であるとき
                now += alist[i]-x+1 # iのアトラクションに何回乗ったか
        return now <= k

    # めぐる式二分探索
    def meguru_bisect(ng, ok):
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok

    n, k = map(int, input().split())
    alist = list(map(int, input().split()))

    ng, ok = -1, 2*10**9+1

    ok = meguru_bisect(ng, ok)

    temp = 0
    cnt = 0

    for i in range(n):
        if alist[i] >= ok:  # Aの中でok以上の数ならば
            cnt += alist[i] - ok + 1  # アトラクションiに乗った回数
            # 初項A公差-1の0までの和と初項ok公差-1の0までの和を引いた値（満足度）
            temp += alist[i]*(alist[i]+1)//2 - ok*(ok-1)//2

    if ok != 0:
        temp += (ok-1) * (k-cnt) # アトラクションの残り回数を使い切る

    print(temp)


if __name__ == '__main__':
    main()

```

### 例題2-7: ABC227 D - Project Planning

https://atcoder.jp/contests/abc227/tasks/abc227_d

#### answer

```python
def main():
    def is_ok(pjt):
        total = 0
        for x in xlist:
            total += min(x, pjt) # プロジェクトでの必要最少人数の合計を計算
        return total >= k * pjt # 合計がプロジェクトの人数とプロジェクトの数以下であるか判定

    def meguru_bisect(ng, ok): # めぐる式二分探索
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok

    n, k = map(int, input().split())
    xlist = list(map(int, input().split()))

    ok = 0
    ng = 10**18 // k

    print(meguru_bisect(ng, ok))


if __name__ == '__main__':
    main()
```


## 3- 自分で実装する例題

### 例題3-1: ABC146 C - Buy an Integer

https://atcoder.jp/contests/abc146/tasks/abc146_c?lang=ja

#### answer

```python
def main():
    a, b, x = map(int, input().split())

    left, right = 0, 10**9+1

    def d(n): # 桁数確認
        return len(list(str(n)))

    while left + 1 != right: # 二分探索
        mid = (left+right)//2
        result = a * mid + b * d(mid)
        if result <= x:
            left = mid
        else:
            right = mid

    return left


if __name__ == '__main__':
    print(main())
```


### 例題3-2: ARC054 B - ムーアの法則 

https://atcoder.jp/contests/arc054/tasks/arc054_b

#### answer

```python
def main():
    import math

    P = float(input())

    def f(x): # f(x)
        return x + P / (2 ** (x / 1.5))

    def fd(x): # f(x)の微分
        return 1 + P * math.log(2**(-1/1.5)) * (2**(-x/1.5))

    left, right = 0, P
    cnt = 10**5 # lim(n->cnt)に近づける

    while cnt > 0: # 二分探索
        cnt -= 1
        mid = (left + right) / 2
        if fd(mid) == 0:
            break
        elif fd(mid) < 0:
            left = mid
        else:
            right = mid

    print(f(mid))


if __name__ == '__main__':
    main()
```

## まとめ

　これだけの問題をやっていたら、競技プログラミングの基本的な二分探索の問題に対応できるだろう。もし、忘れてしまったら、また、この記事に立ち返って復習をしていただけると幸いだ。