Pythonでアルゴリズム（二分探索）

はじめに

　コロナウイルスの影響で暇になったので...（以下略）
　前回のセグ木は重かったので今回は割と簡単に実装できる二分探索を適当にまとめてみます。

考え方

　どこかの境界で条件を満たすものと満たさないものが分かれている場合に、その境界をO(logN)で探索することができます。
　例えば、条件を満たさないものをx、満たすものをoとして、以下のようなリストが与えられたとします。
　　　　　　　　　　　xxxxxxoooooo

　0-indexで考えると、5番目や、6番目(境界の左右どちらか)を求めたいというときに二分探索が有効です。
　探索する範囲の左をleft、右をrightという変数に代入します。これらを足して、2で割ったもの（切り捨て）をmidとして、indexがmidの要素が条件を満たすかどうかを判定します。
　満たすなら、それよりも右には境界はないのでrightの値をmidに更新して右側を切り捨てます。逆に、満たさないならそれよりも左に境界はないのでleftの値をmidに更新します。
　このようにして毎回半分ずつ区間が狭くなり、最終的にはrightとleftが隣り合ったら探索終了です。このとき、rightは常に条件を満たす要素のインデックス、leftは満たさないもののインデックスを持たせていたので、上の例でいうとleftは5、rightは6という値を持ちます。

例題1

　[2, 5, 7, 9, 10, 18, 29]で、9以上となる最小のインデックスを考える。これは、条件を9以上とすれば満たすか満たさないかがxxxooooとなるため最終的にrightが持つ値が答え。　

コード

a = [2, 5, 7, 9, 10, 18, 29]

left = 0
right = len(a) - 1

while right - left > 1:
    mid = (right + left) // 2
    if a[mid] >= 9:
        right = mid
    else:
        left = mid

print(right) # 3

例題2

　せっかくなのでatcoderの過去問から、ABC146-CのBuy an integerを解きます。これも、候補である1~10^9についてどこかより左は買えて、右は買えないという境界が存在するため二分探索していけばよい。今回はインデックスでなく直接整数を探索します。(リスト作ってたらTLEです)
　注意として、1つも買えない場合とすべて買える場合には境界が存在しないため場合分けした方がよさそうです。

コード

import sys

a, b, x = [int(x) for x in input().split()]

left = 1
right = 10**9

if a*right + b*len(str(right)) <= x:
    print(right)
    sys.exit()

if a*left + b*len(str(left)) > x:
    print(0)
    sys.exit()

while right - left > 1:
    mid = (right + left) // 2
    if a*mid + b*len(str(mid)) <= x:
        left = mid
    else:
        right = mid

print(left)

標準ライブラリbisect

　リストの中に含まれるか判定する二分探索、挿入したい要素の入るインデックスを求める際に使えます。
　これは、昔自作したものもあるので自作してもよいですが、標準ライブラリのbisectを使うのが普通だと思います。(使い方は練習必要な気がします)