二分木探索

今回は二分木探索をやっていきます。
以下の記事で使ったことがあるので、その問題で今回はやっていきます。
コードもそこから流用します。
nasubifx.hatenablog.com

問題URL
https://atcoder.jp/contests/abc146/tasks/abc146_c

二分木探索を使う場合は全探索で間に合わない場面で使います。
今回は範囲は10**9ということで探索で間に合いません。
ここは二分木探索の探索範囲を決定しています。

A,B,X=map(int,input().split())

left=1
right=10**9
ans=0

ここが、二分木探索の処理になります。

while left<=right:
    mid=(left + right)// 2 
    #Xより小さい場合に探索範囲を右に変える
    if A*mid+B*len(str(mid))<=X:
        ans=mid
        left=mid+1
    #Xより大きい場合に探索範囲を左に変える
    else:
        right=mid-1
        
print(ans)

簡単に二分木探索をしておきます。
まず、大前提として、配列の場合はソートしてある必要があります。
二分木探索は常に中央の値が求めている値と比較して小さいか、大きいかで次の探索範囲を決める。これによって、探索範囲が半分になっていき全探索ではできなかった広い範囲も探索できるようになります。

探索範囲の変え方については画像を見れば分かるとおり、探索範囲を右に変える場合は left=mid+1、探索範囲を左に変えるright=mid-1となっている。
今回の問題は特定の値ではなく、最も大きい整数を求めるのでmidがXより小さいとき、答えの変数に格納midを格納しておきそれをどんどん更新していく形にしている。
二分木探索の終了の条件は画像の通り１つの数値しか残らないのでleft<=rightとしている。

A,B,X=map(int,input().split())

left=1
right=10**9
ans=0

while left<=right:
    mid=(left + right)// 2 
    #Xより小さい場合に探索範囲を右に変える
    if A*mid+B*len(str(mid))<=X:
        ans=mid
        left=mid+1
    #Xより大きい場合に探索範囲を左に変える
    else:
        right=mid-1
        
print(ans)

今回は二分木探索をやりましたが、動的計画法(DP)と比べると複雑ではないので、簡単なアルゴリズムでした。