二分探索とは
二分探索（バイナリサーチ）とは、かんたんにいうと、数字がソートされたリストのなかから、求めたい数を効率的に求めるための手法である。
例えば、次のようなリストがあったとしよう。
[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つあるのは、重複した値に対する操作である。以下のようなコードでは、同じ値がある場合、それぞれの端の値を返すようになっている。
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))
# output
>> 7
>> 9
insort
次に、insortについて説明する。これは、insort(リスト、挿入したい値)と書き、リストの順序を崩さずに、値を挿入することができる。例えば、次のようにだ。
from bisect import insort
numbers = [0, 1, 3, 4, 5, 6, 8, 9]
insort(numbers, 2)
print(numbers)
insort(numbers, 7)
print(numbers)
# output
>> [0, 1, 2, 3, 4, 5, 6, 8, 9]
>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
その他メソッドはこちらの公式ドキュメントに記載されている。
手法2: めぐる式二分探索
めぐる式二分探索とは、次のようなコードの二分探索のことをいう。
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で実装
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（再帰関数）で実装
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
answer
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 - 飛行機乗り
answer
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
answer
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
answer
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
answer
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
answer
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
answer
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
answer
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
answer
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 - 億マス計算
answer
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
answer
# 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 - 射撃王
answer
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 - 食塩水
answer
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
answer
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 - 花束
answer
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
answer
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
answer
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
answer
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
answer
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 - ムーアの法則
answer
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()
まとめ
これだけの問題をやっていたら、競技プログラミングの基本的な二分探索の問題に対応できるだろう。もし、忘れてしまったら、また、この記事に立ち返って復習をしていただけると幸いだ。