okinawa

IT勉強メモ

二分探索

競技プログラミング

二分探索とは

二分探索とは、データ検索アルゴリズムの一つで、ソート（整列）済みのデータ群の探索範囲を半分に絞り込むを操作を繰り返すことで高速に探索を行う手法。 二分探索（2分探索 / バイナリサーチ）とは - 意味をわかりやすく - IT用語辞典 e-Words

・ポイント

探索のたびに探索範囲が半分になるから高速。

ソート済みじゃないとダメ。

・競プロ用ポイント

めぐる式二分探索というのがバグりにくい。

条件を満たす最小を求めるか、最大を求めるかで若干コードを変える。

理解のポイント

OKは常に条件を満たすことが確定したエリアにいる。

NGは常に条件を満たさないことが確定したエリアにいる。

自力実装

条件を満たす最小の値を求める

# ok･･･条件を満たすなかで最小のindex。左側をOKにする
# ng･･･条件を満たさないなかで最大のindex。右側をNGにする
def is_ok2(i):
   return i <= 5

ok = 1 #左側(解が存在する値)
ng = 11 #右側(解が存在しない値)
while abs(ok-ng) > 1:
    mid = (ok+ng) // 2 
    if is_ok2(mid):
        ok = mid
    else:
        ng = mid
print(ok,ng) # "5 6" が出力される

条件を満たす最大の値を求める

# ok･･･条件を満たすなかで最大のindex。右側をOKにする
# ng･･･条件を満たさないなかで最小のindex。左側をNGにする
def is_ok(i):
   return i > 5

ok = 10 #右側(解が存在する値)
ng = -1 #左側(解が存在しない値)
while abs(ok-ng) > 1:
    mid = (ok+ng) // 2 
    if is_ok(mid):
        ok = mid
    else:
        ng = mid
print(ok,ng) # "6 5" が出力される

参考サイト

zenn.dev

qiita.com

bisect関数

import bisect
ls1 = [1,2,2,3,4,5]

#bisect(ソート済みリスト, 探索したい値)
print(bisect.bisect_left(ls1, 2)) #1　挿入できる値の左INDEXを返す
print(bisect.bisect_right(ls1, 2)) #3 挿入できる値の右INDEXを返す
print(bisect.bisect(ls1, 2)) #3 同上

番兵の活用方法

・実データには出現しない、データの終了を表すための専用の値
・入力データを処理するループの終了条件が複数ある場合に、条件判定の数を削減するために置くダミーのデータ
番兵 - Wikipedia

2分探索で配列外参照にならないように、両端に番兵を置く。

import bisect
ls1 = [1,2,2,3,4,5]
i = bisect.bisect_left(ls1, 8) #6。配列外のINDEXが返る
ls1[i] # 配列外参照エラー

ls1 = ls1 + [-1*10**9, 10**9]#両端に番兵を追加
ls1.sort()
i = bisect.bisect_left(ls1, 6) #6。5と10**9の間のINDEX
ls1[i] # 1000000000
print(ls1) #[-1000000000, 1, 2, 2, 3, 4, 5, 1000000000]

・参考

例題

atcoder.jp

atcoder.jp

atcoder.jp