概要
atcoderなどで二分探索の問題が出た際に、さらっと参照するための記事です。
細かな説明は、アルゴリズムの解説サイトなどを見た方が良いと思います。
二分探索について
二分探索とは、集合{1,2,3,...,N}が線形的に変化する際に、端から順に調べるのではなく、
真ん中を探索していく方法です。
例えば、[1, 3, 5, 7, 9]の配列から4より大きい数の個数を求める場合、配列の数字は単調に増加しているため、真ん中（インデックス2）の5が
4より大きければ、5より右側は全て4より大きいことが分かります。
そうすると、今度は5より左側のみを調べればよいので、[1, 3, 5]の真ん中の3を調べて4より小さいから...
といった流れで、わずか2回の計算で配列のどこからどこまでが4より小さいのかが分かります。
今回の場合は、配列の長さが5だったため、全探索の回数5に対して、二分探索では2と差が少なかったですが、
Nが大きければ大きいほどその差は歴然です。
以下から、実際の利用方法を見ていきましょう。
利用方法
使い方は非常に簡単で、端と端を定義し、真ん中を調べた時の結果に応じて右端もしくは左端を再定義します。
実際に問題を見た方が早いと思いますので、以下から早速、一緒に解いていきましょう。
引用元：典型アルゴリズム問題集
上の問題は、すでにソート済みの数列の中から、K以上である、最小のものをみつける問題です。
入力
N K
A0 A1 ⋯ AN−1
# 入力を受け取る
N, K = map(int, input().split())
A = list(map(int, input().split()))
# 配列の右端をok, 左端をngと設定する。それぞれ端から１ずれているのは、両端が未判定のため。
ok = N
ng = -1
# while文で繰り返し真ん中の値を調べていく。while文を抜け出す条件は、okとngが隣り合う（差が1になる）まで
while abs(ok - ng) > 1:
# 真ん中の値をmidに代入
mid = (ok + ng) // 2
# 真ん中の値がK以上ならokにmidを、そうでなければ、ngにmidを代入
if A[mid] >= K:
ok = mid
else:
ng = mid
# whileの処理により、okに入っている値は、K以上を満たす最小の値。
# okが最初の値と変わっていない時、条件をみたすものがない。
if ok != N:
print(ok)
else:
print(-1)
終わりに
二分探索は長さNの配列をlogNで計算できる非常に強力なアルゴリズムです。
※例えば、10^9の計算がわずか20回程で終わります。
それゆえに、様々な活用方法があり、今回の記事では、最初から与えられた数列がソートされていましたが、
場合によっては自身でソートしたり、単調に変化するものを見出して二分法を活用する場合もあります。
ぜひ、この記事を読まれた方は、@e869120さんが書かれた分野別 初中級者が解くべき過去問精選 100 問などで練習問題をこなし、活用の幅を広げてみてください。
ここまで、お読みいただきありがとうございました。