二分探索(binary search)について
概要
- linear searchに比べて計算量がlogで落ちる
- 1024までの探索は2^10回で済む
- pure pythonでも実装することができ、シンプルでわかりやすい
- また、ギリギリ条件が成立する領域の探索にも使うことができる
- かんたんにも止まらない最小値・最大値を求めるとき、微分することや条件を変えることが求められる
- ランダウ表記では
O(n)がO(log n)になる
テンプレート
def is_ok(n):
return "boolean"
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
print(meguru_bisect(0, 10**20))
- ニーズに応じで
ng,okを反転したりする
ライブラリによる使用例
cpp
std:upper_bound(vec.begin(), vec.end(), key); // vecのiteratorを返す
std:upper_bound(vec.begin(), vec.end(), key) - vec.begin(); // vecのindexを返す
std:lower_bound(vec.begin(), vec.end(), key); // vecのiteratorを返す
std:lower_bound(vec.begin(), vec.end(), key) - vec.begin(); // vecのindexを返す
upper_bound- key以上のvalueを持つindexを返す
lower_bound- keyより大きいvalueを持つindexを返す
python
bisect.bisect_left(vec, key)
bisect.bisect_right(vec, key)
bisect.bisect_left- リストを左からみて、順番を維持するのに入れると良さそうな位置
bisect.bisect_right- リストを右からみて、順番を維持するのに入れると良さそうな位置
pythonでの例
import bisect
A = [1, 1.5, 2, 2.5, 3, 3, 3.5, 4, 4.5, 5]
# 0 1 2 3 4 5 6 7 8 9
assert bisect.bisect_left(A, 2.99) == 4,"リストを左から見ていって入れると良さそうな場所"
assert A[bisect.bisect_left(A, 2.99)] == 3, "3の位置に2.99をinsertすると良さそう"
assert bisect.bisect_right(A, 3) == 6, "リストを右から見ていって、入れると良さそうな場所"
assert A[bisect.bisect_right(A, 3)] == 3.5, "3.5の位置に3をinsertすると良さそう"
assert bisect.bisect_left(A, 0.5) == 0, "0番目の位置に入れると良さそう"
assert bisect.bisect_right(A, 6) >= len(A), "満たす要素がないから最大インデックス以上"
pythonでのキー(関数)を与えたレシピ
class KeyifyList(object):
def __init__(self, inner, key):
self.inner = inner
self.key = key
def __len__(self):
return len(self.inner)
def __getitem__(self, k):
return self.key(self.inner[k])
if __name__ == '__main__':
import bisect
L = [(0, 0), (1, 5), (2, 10), (3, 15), (4, 20)]
assert bisect.bisect_left(KeyifyList(L, lambda x: x[0]), 3) == 3
assert bisect.bisect_left(KeyifyList(L, lambda x: x[1]), 3) == 1
pure pythonによる実装例
- pure pythonによる実装例
# Iterative Binary Search Function
# It returns index of x in given array arr if present,
# else returns -1
def binary_search(arr, x):
low = 0
high = len(arr) - 1
mid = 0
while low <= high:
mid = (high + low) // 2
# If x is greater, ignore left half
if arr[mid] < x:
low = mid + 1
# If x is smaller, ignore right half
elif arr[mid] > x:
high = mid - 1
# means x is present at mid
else:
return mid
# If we reach here, then the element was not present
return -1
# Test array
arr = [ 2, 3, 4, 10, 40 ]
x = 10
result = binary_search(arr, x)
if result != -1:
print("Element is present at index", str(result))
else:
print("Element is not present in array")
例; なんとかして評価式を作って評価式が成立しているか確認する二分探索
問題
解説
- この式は上限が成立する最大値を求めるもの
ok,ng構文が使えるので楽に二分探索できる
解答
R,B=map(int,input().split())
X,Y=map(int,input().split())
def check(n):
r = R-n
b = B-n
if r < 0 or b < 0:
return False
if r//(X-1) + b//(Y-1) >= n:
return True
else:
return False
def meguru_bisect(ng, ok):
while (abs(ok - ng) > 1):
mid = (ok + ng) // 2
if check(mid):
ok = mid
else:
ng = mid
return ok
print(meguru_bisect(ng=10**20, ok=0))
例; 表題で説明されている指標ではなく、とりうる時間に着目して二分探索する例
問題
解答
例; 最大値のリストの最小値の最大値を知りたい
問題
min(max(e0, e1,...), max(f0, f1,...), ...)を知りたいような場合、機械的な操作が入るので二分探索ができるような気がしないが、実際は各々の構成要素がk以上であることを求める二分探索にすることができる
感覚的には結びつかないので、何らか工夫する必要がある
解答
N = int(input())
A = [tuple(map(int, input().split())) for i in range(N)]
def check(x):
s = set()
for a in A:
s.add(sum(1 << i for i in range(5) if a[i] >= x))
for x in s:
for y in s:
for z in s:
if x | y | z == 31:
return True
return False
ok = 0
ng = 10**9 + 1
while ng - ok > 1:
cen = (ok + ng) // 2
if check(cen):
ok = cen
else:
ng = cen
print(ok)
例; 整数ではない解を持つ最大値を求める -> 微分して初めて負になる点を求める
問題
解説
- 整数ではない二分探索の例
- 左から見ていって初めて単調増加でなくなる点 ＝ 微分して初めてマイナスになる点を探す
解答1
P = float(input())
def f(x):
return x + P*(2**(-x/1.5))
def check(n):
d = (10**-9)
return f(n+d) - f(n) < 0
ok = 0
ng = P
while True:
mid = (ok + ng) / 2
if check(mid):
ok = mid
else:
ng = mid
if ng - ok < 10**-8:
break
print(f(ok))
解答2
- 微分した式を直接評価する
import math
P = float(input())
def f(x):
return x + P*(2**(-x/1.5))
def is_ok(x):
# x + P*(2**(-x/1.5)) を微分すると
# 1 + P * 2**(-x/1.5) * log 2 * (-1/1.5)
if 1 + P * 2**(-x/1.5) * math.log(2) * (-1/1.5) > 0:
return True
return False
def meguru_bisect(ng, ok):
while (abs(ok - ng) > 0.000000001):
mid = (ok + ng) / 2
if is_ok(mid):
ok = mid
else:
ng = mid
print(f(ok))
meguru_bisect(0, 10**20)
例; ある値より大きいかつ、ある値より小さいのindexを求める
問題
解説
- bisectのモジュールだけでは
x値以上のものを検索する関係上、正しい答えが得られない - そのため二分探索をフルスクラッチする必要がある
解答
N = int(input())
A = sorted(list(map(int,input().split())))
B = list(map(int,input().split()))
C = sorted(list(map(int,input().split())))
ans = 0
for n in range(N):
b = B[n]
l = 0
r = len(A)
while l < r:
mid = (l+r) // 2
if A[mid] < b:
l = mid + 1
else:
r = mid
ai = l
l = 0
r = len(C)
while l < r:
mid = (l+r) // 2
if b < C[mid]:
r = mid
else:
l = mid + 1
ci = l
ans += ai*(N-ci)
print(ans)
インタラクティブに二分探索をする問題
問題
解説
- 解が含まれる範囲は、偶数範囲で端同士が同性、奇数範囲では端同士が異性
- 解が含まれる範囲をTrueとして二分探索することで解が得られる
解答
N = int(input())
print(0, flush=True)
r = input()
if r == "Vacant":
exit()
init = r
def query(mid):
print(mid, flush=True)
r = input()
if r == "Vacant":
exit()
return int(r != init) # 相違していたら1
def meguru_bisect(ng, ok):
while (abs(ok - ng) > 1):
mid = (ok + ng) // 2
# ng条件: mid%2 == 0のときqueryが相違(vacantが含まれない)
# : mid%2 == 1のときqueryが一致
if query(mid) == mid%2:
ng = mid
else:
ok = mid
return ok
meguru_bisect(0, N)