競技プログラミングでは探索はとても重要な要素です。
二分探索は効率的なアルゴリズムで、習得すべき必須要素です。
この記事では、二分探索の基本的な概念から実装方法まで詳しく解説します。
二分探索とは
二分探索は、ソートされたリストなどから特定の要素を高速に見つけるためのアルゴリズムです。
基本的な概念
二分探索は、検索のたびに探索範囲を絞り込んでいきます。
ソートされたデータの真ん中値について、検索する値との大小関係を比較して、次の探索範囲を半分にします。
この操作を繰り返して検索する値を高速に見つけることができます。
なぜ二分探索が効率的？
データの先頭の要素から順番に検索していく線形探索では、最悪の場合、要素すべてを見る必要があります。
たとえば、1万個のデータの中から検索するとき、一番最後の要素が検索対象である場合は、1万回検索する必要があります。
二分探索では、探索範囲を1回の検索で半分に減らすため、検索の回数が大幅に減ります。
二分探索のイメージ
二分探索のアルゴリズムは次のようになります。
データの中央の値と大小関係を比較して、探索範囲を絞っていきます。
二分探索は境界を見つける
二分探索は、値を見つけるだけではなく、境界を見つけるのにも役立ちます。
めぐる式二分探索
二分探索の実装にはいろいろな方法がありますが、この記事ではめぐる式二分探索と呼ばれるコードについて紹介します。
実装コード
基本的なコードは次のようなものになります。
ng は条件を満たさない値、ok は条件を満たす値を設定します。
先ほどの図のように、条件を満たさないゾーンと条件を満たすゾーンをどんどん狭めていき、最終的にその境界を求めます。
# 条件を満たすか判定する関数
def is_ok(index, key):
# 条件を満たすか判定する処理
def binary_search(key):
ng = -1 # 解が存在しない値
ok = len(a) # 解が存在する値
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_ok(mid, key):
ok = mid
else:
ng = mid
return ok配列 a について、key 以上のインデックスを求めるコードの場合、次のようになります。
a = [1, 2, 3, 3, 5, 5, 5, 6]
def is_ok(index, key):
if a[index] >= key:
return True
else:
return False
def binary_search(key):
ng = -1
ok = len(a)
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_ok(mid, key):
ok = mid
else:
ng = mid
return ok
print(binary_search(0)) # => 0
print(binary_search(1)) # => 0
print(binary_search(2)) # => 1
print(binary_search(3)) # => 2
print(binary_search(4)) # => 4
print(binary_search(5)) # => 4
print(binary_search(6)) # => 7
print(binary_search(7)) # => 8検索する値の境界が見つかっているのが確認できます。
bisect
Python では、二分探索するためのライブラリが用意されています。
使うためには、bisect をインポートする必要があります。
import bisectbisect
bisect はソートされたリスト a について、値 x を挿入する位置を返します。
- bisect.bisect_left(a, x)： a に挿入できる一番 左 の位置
- bisect.bisect_right(a, x)： a に挿入できる一番 右 の位置
リストの中に挿入する値が複数あるときに変わってきます。
import bisect
a = [1, 2, 3, 3, 5, 5, 5, 6]
print(bisect.bisect_left(a, 0)) # => 0
print(bisect.bisect_right(a, 0)) # => 0
print(bisect.bisect_left(a, 4)) # => 4
print(bisect.bisect_right(a, 4)) # => 4
print(bisect.bisect_left(a, 8)) # => 8
print(bisect.bisect_right(a, 8)) # => 8
# 挿入する値が複数あるとき
print(bisect.bisect_left(a, 5)) # => 4
print(bisect.bisect_right(a, 5)) # => 7
insert
insert を使えば挿入することもできます。
- bisect.insert_left(a, x)： a に挿入できる一番 左 の位置に挿入
- bisect.insert_right(a, x)： a に挿入できる一番 右 の位置に挿入
import bisect
a = [1, 2, 3, 3, 5, 5, 5, 6]
bisect.insort_left(a, 3)
print(a) #=> [1, 2, 3, 3, 3, 5, 5, 5, 6]
bisect.insort_right(a, 5)
print(a) # => [1, 2, 3, 3, 3, 5, 5, 5, 5, 6]問題を解く
AtCoder の問題を二分探索を使って解いてみます。
典型アルゴリズム問題集 A – 二分探索の練習問題
めぐる式二分探索で解く
N, K = map(int, input().split())
A = list(map(int, input().split()))
def is_ok(index, key):
return A[index] >= key
def binary_search(key):
ng = -1
ok = len(A)
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_ok(mid, key):
ok = mid
else:
ng = mid
return ok
answer = binary_search(K)
if answer == N:
print(-1)
else:
print(answer)bisect で解く
bisect を使って解いたコードになります。
import bisect
N, K = map(int, input().split())
A = list(map(int, input().split()))
answer = bisect.bisect_left(A, K)
if answer == N:
print(-1)
else:
print(answer)ABC231 C – Counting 2
この問題では、条件を満たす数を求める必要があります。
条件を満たす数は、リストの要素数から二分探索で求めた値を引くことで求めることができます。
めぐる式二分探索で解く
N, Q = map(int, input().split())
A = list(map(int, input().split()))
# 二分探索のためにソート
A.sort()
def is_ok(index, key):
return A[index] >= key
def binary_search(key):
ng = -1
ok = len(A)
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_ok(mid, key):
ok = mid
else:
ng = mid
return ok
for _ in range(Q):
x = int(input())
# x 以上の数を求める
answer = N - binary_search(x)
print(answer)bisect で解く
import bisect
N, Q = map(int, input().split())
A = list(map(int, input().split()))
# 二分探索のためにソート
A.sort()
for _ in range(Q):
x = int(input())
# x 以上の数を求める
answer = N - bisect.bisect_left(A, x)
print(answer)ABC146 C – Buy an Integer
めぐる式二分探索の ng と ok 、条件を満たすか判定する処理を変更して解くことができます。
A, B, X = map(int, input().split())
def is_ok(N, key):
price = A*N + B*len(str(N))
return price <= key
def binary_search(key):
ng = 10**9 + 1
ok = 0
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_ok(mid, key):
ok = mid
else:
ng = mid
return ok
print(binary_search(X))
