二部探索ライブラリ

二部探索をしてくれるPythonライブラリです。
Pythonのbisectモジュールはソートされたリストにしか対応しておらず、単調増加関数に対する二部探索は自分で書く必要があります。以前のものより小回りが利くようにクラスモジュールで定義しました。

class BisectSearch:
    def __init__(self, f, l=0, r=10**9):
        self.f = f
        self.l = l
        self.r = r
    def __call__(self, dist):
        f = self.f
        l = self.l
        r = self.r
        if dist <= f(l):
            return l
        if f(r) <= dist:
            return r
        while r-l > 1:
            n = (r+l) // 2
            if f(n) <= dist:
                l = n
            else:
                r = n
        return l

入力

$l, r$ ... 閉区間 $[l, r$ ] で探索したい範囲を指定します。
$f$ ... $[l, r$ ] $\mapsto \mathbb{R}$ となる単調増加関数 $f$ を指定します。
$\mathrm{dist}$ ... 探索したい値を指定します。

出力

$f(t) \le dist \lt f(t+1)$ を満たすときの $t$ を返します。ただし $dist \lt f(l), f(r) \le dist$ のときはそれぞれ $l, r$ を返します。

使用例

使用したコードがあれば適宜アップデートしていきます。

AtCoder ABC 146 C - Buy an Integer

class BisectSearch:
    # Folding

a, b, x = map(int, input().split())
def f(n):
    return a*n + b*len(str(n))
print(BisectSearch(f, l=0, r=10**9)(x))

AtCoder CODE FESTIVAL 2014 決勝 - C - N進数

class BisectSearch:
    # Folding

a = int(input())
def f(n):
    return sum(int(s) * n**i for i, s in enumerate(str(n)[::-1]))
k = BisectSearch(f, 1, 10**16)(a)
print(k if f(k) == a and k >= 10 else -1)

AtCoder CODE FESTIVAL 2016 Final B - Exactly N points

class BisectSearch:
    # Folding

n = int(input())
def f(n):
    return (n+1)*n // 2
m = BisectSearch(f, l=1, r=10**7)(n)
m += f(m) != n
A = set(range(1, m+1))
A.discard(f(m) - n)
print(*A, sep='\n')