二分探索 - ysknsid25/atcoder GitHub Wiki

結論を言うと二分探索の計算量はlogNだ。

指数と対数

二分探索の計算量を考えるにあたってこれが必要。いや、それ抜きにしても指数対数は重要なんだがそれはおいておき…なんで指数と対数が出てくるかというと、二分探索の計算量は対数的に増加するからだ。そして対数を説明するにはセットで指数を説明する必要がある。なのでこの順番で説明する。

それぞれひとことで説明するとこんな感じ。さすがに指数は分かるだろう。が、普段意識しない対数は忘れがち。

指数 = xをk回かけたらnになる。n = xk

対数 = xがnになるにはk回掛ける k=logXN

つまり、指数も対数も考えてることはxにkを掛けることなのだ。それを指数はnから見ていて、対数はkから見ているだけ。

そして指数の場合はk(掛ける回数)が増えるとnがどんどん大きくなる。逆に対数の場合はnがどれだけ増えてもkはそれほど増えない。これはグラフで書くとよくわかる。以下は先の数式をx=2, kを0~10の範囲で増加させた場合のグラフだ。なんかこんなグラフ高校二年生くらいの頃に見たよね。

二分探索

ソート済みのデータ列があったとする。この中から目標の値を探すのが二分探索だ。

方法はシンプルで、常に中央の値を確認しながら、探索範囲を半分に絞っていく。

例えば、以下のような昇順の配列を考えよう。

[1, 3, 5, 7, 9, 11, 13, 15]

このような配列に対して9を効率的に探索する方法を考える。

中央（インデックス 3 の値 7）を見る → 7 < 9 なので右側に絞る → [9, 11, 13, 15] が新しい探索範囲（半分に縮小）
次の中央（インデックス 5 の値 11）を見る → 11 > 9 なので左側に絞る → [9] が新しい探索範囲（また半分に縮小）
残った 9 を確認 → 見つかった！

となる。今回は8つしか数値がないので前から見ても後ろから見てもすぐに見つかる。が、これが1000000個の数値とかが一意に並んでると順番に見ていく方法は効率が悪い。なので二分探索という方法が有効になる。具体的にどのくらい差が出るのかはこのあと実際に計算量を比較する。

二分探索の計算量を考える

先の例を使ってn=8のとき、前から見る方法と二分探索する方法で計算量を比較する。

まず前から見た時だが、最悪の場合を想定するとn番目に見つかることになるので計算量はO(n)だ。

一方で二分探索の場合、探索範囲は以下のように変化する。

n/2 (もとの半分を探す。n=8のとき、4つを探すことになる)
n/4 (さらに半分を探す。n=8のとき、2回目では2つを探すことになる)
n/8 (さらに半分を探す。n=8のとき、ここで残った1つに行き当たる)

つまり、もともとn個あるデータが1個になるまでk回半分にしていくってことだ。

これを一般化するとn/2^k=1となる。さらにこの式を解くとn=2^Kとなる。

二分探索の計算回数はnが幾つであろうが2で割る回数(=k)で決まる。だから二分探索の計算量は実質kで評価されることになる。しかし先に前から見た時の計算量はnで表現しているため、今回もnを使って表現したい。そのために対数で表現する必要がある。対数で表現するとk=log2Nとなる。計算量を考える場合2という固定値は無視できるため、最終的に計算量はO(logN)となる。

以上で前から見た時と二分探索した時で計算量が違うことがわかった。前から見た時はO(n)。二分探索した時はO(log n)だ。よってn=8の場合の計算量は前から見た時は8。二分探索すると3となる。つまり数列の中から特定の値を一つ探索する場合は、二分探索を行う方が計算量が小さい。

Pythonで二分探索するならbisectを使う

bisect_left(a, x)

x を挿入できる最も左側の位置を返すすでに x が a に存在する場合、その要素の左側のインデックスを返す

bisect_right(a, x)

x を挿入できる最も右側の位置を返すすでに x が a に存在する場合、その要素の右側のインデックスを返す

例題: ABC382 C

順番は逆だったんだけど、この問題を解くにあたってbisectが有効に使える。ただし、そのまま使えない。つまり少し応用が必要ってことで、使い方として馴染ませるのにはもってこいの良問だ。

C - Kaiten Sushi

美味しさの閾値を上回っていれば、回転寿司の出口に近いところにいる人からその寿司を取っていくという問題。

考え方

要はあらかじめ美味しさの閾値が低い順に人の位置をメモしておく。同じ閾値であれば、最初に出てきた人の位置を記録する。つまり左から順に都度その時点での最小の美食度とその人の位置を記録しながらAを全探索する。この探索の結果はkey: 美食度, value:位置のdictと美食度の集合に突っ込んでおく。

あとは流れてくる寿司の美食度を順に美食度の集合を二分探索する。このときはbisect_rightを使って探索し、見つかった位置が0なら0。0でなければ見つかった位置-1した値が答えとなる。

-1の場合の考慮はコードを見てもらえればよい。僕は以下のように実装した。

import bisect
from collections import defaultdict

n,m=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

searched = defaultdict(int)
gastronomy_list = [A[0]]
whose_gastronomy = {}
whose_gastronomy[A[0]] = 0
current_min = A[0]
total_min = A[0]

for i in range(1, n):
    if searched[i]==1:
        continue
    if A[i] < current_min:
        current_min = A[i]
        gastronomy_list.append(A[i])
        whose_gastronomy[A[i]] = i
        total_min = A[i]
    searched[i] = 1

gastronomy_list.sort()
print(whose_gastronomy)

for b in B:
    if b < total_min:
        print(-1)
        continue
    who = bisect.bisect_right(gastronomy_list, b)
    print(who, b)
    if who==0:
        print(whose_gastronomy[gastronomy_list[0]]+1)
    else:
        print(whose_gastronomy[gastronomy_list[who-1]]+1)