旧 Python 二部探索デコレータ関数

追記（2020/07/15）

二部探索用コードはアップデートされました。 ⇨更新先サイト

二部探索デコレータ関数

二部探索用のPythonコードのメモ書きです。 デコレータを使っていい感じにしてます。

def bisect_search(l=0, r=10**6):
    def _bisect_search(f, l=l, r=r):
        if not f(l):
            return l
        if f(r):
            return r
        while r-l > 1:
            n = (r+l) // 2
            if f(n):
                l = n
            else:
                r = n
        return l
    return _bisect_search

解説

... 閉区間で探索したい範囲を指定します。
... intからboolの写像です。定義域のある値を境に値域がTrue⇒Falseになるような単調な写像である必要があります。

使用例

現状少ないので情報をくれればアップデートします。

AtCoder ABC 146 C - Buy an Integer

from math import log10
inputs = open(0).read().split('\n')
 
def bisect_search(l=0, r=10**6):
    def _bisect_search(f, l=l, r=r):
        if not f(l):
            return l
        if f(r):
            return r
        while r-l > 1:
            n = (r+l) // 2
            if f(n):
                l = n
            else:
                r = n
        return l
    return _bisect_search
  
a, b, x = map(int, inputs[0].split())
@bisect_search(l=0, r=10**9)
def f(n):
    return n == 0 or a*n + b*int(log10(n)+1) <= x
print(f)