3-1 値の探索だけじゃない！”二分探索”

二分探索は以下のような状況で利用できる。

実数や整数に対して統一的に定義される条件について、ある値 $x$ が存在して、 $x$ 以上では常に条件が成立する / しない、かつ $x$ 未満では常に条件が成立しない / する

即ちある条件 C に対して定義域内での条件が False, False, ..., False, False, True, True, ..., True, True となる場合、二分探索は False と True の境界を求めることであると表現出来る。

💡

しばしば二分探索の例として、単調増加の数列 a において任意の値 x 以上での最小の値の探索が挙げられるが、この場合でも条件 C を「 x より大きい」と定めれば、上述の一般化に当てはめる事が出来る。

例)

a = {1, 3, 4, 6, 8, 9}
x = 5

C(a) -> {False, False, False, True, True, True}

ソート列から値を探す

# lower_bound
 
n: int
k: int
a: list[int]
 
 
def solve() -> None:
    lo = -1
    hi = n
    c = lambda x: a[x] >= k
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if c(mid):
            hi = mid
        else:
            lo = mid
    print(hi)

>>> n = 4
>>> k = 1
>>> a = [2, 3, 3, 5]
>>> solve()
0

💡

終了条件は hi-lo=1 であり、最終的に hi の値が返されるため、 lo=-1 で初期化する。（ x が min(a) より小さい場合に hi=0 になり得ないため）

解を仮定し可能か判定

# Cable master
 
N: int
K: int
L: list[float]
 
 
def solve() -> None:
    lo = 0
    hi = max(L)
    c = lambda l: sum(rope // l for rope in L) < K
    while hi - lo > 1e-5:
        mid = (hi + lo) / 2
        if c(mid):
            hi = mid
        else:
            lo = mid
    return round(lo, 2)

>>> N = 4
>>> K = 11
>>> L = [8.02, 7.43, 4.57, 5.39]
>>> solve()
2.0

最小値の最大化

# Aggressive cows
 
N: int
M: int
x: list[int]
 
 
def c(d):
    pre_i = 0
    remain = M - 1
    for i in range(1, N):
        if x[i] - x[pre_i] >= d:
            remain -= 1
            pre_i = i
    return remain > 0
 
 
def solve() -> None:
    x.sort()
 
    lo = 0
    hi = max(x)
    while hi - lo > 1:
        mid = (hi + lo) // 2
        if c(mid):
            hi = mid
        else:
            lo = mid
    return lo

>>> N = 5
>>> M = 3
>>> x = [1, 2, 8, 4, 9]
>>> solve()
3

平均最大化

条件 C を「単位当たり重さの価値が x 以上となるように選ぶことが出来る」と定めると、条件を満たす最大の x を求める問題となる。

条件 C の判定は

\begin{aligned} \sum_{i\in S}v_{i} / \sum_{i\in S}w_{i} &\geqq x \\ \sum_{i\in S}v_{i} &\geqq x \times \sum_{i\in S}w_{i} \\ \sum_{i\in S}v_{i} - x \times \sum_{i\in S}w_{i} &\geqq 0 \\ \sum_{i\in S}(v_{i} - x \times w_{i}) &\geqq 0 \end{aligned}

により、各 v, w について v - x * w を計算し、大きいものから k 個選んだときの和が 0 を超えるかどうか判定すればよい。

💡

$(w_{1}, v_{1}), (w_{2}, v_{2})$ について、 $\frac{v_{1}}{w_{1}} + v_{2}/w_{2} \not= (v_{1}+v_{2}) / (w_{1}+w_{2})$ のため、重さ当たりの価値が最大となる商品を選択する貪欲的な解法は適用できない。

# 平均最大化
 
n: int
k: int
w: list[int]
v: list[int]
 
 
def c(x):
    return sum(sorted(map(lambda w, v: v - x * w, w, v), reverse=True)[:k]) < 0
 
 
def solve() -> None:
    lo = 0
    hi = max(v)
    while hi - lo > 1e-5:
        mid = (hi + lo) / 2
        if c(mid):
            hi = mid
        else:
            lo = mid
    return round(hi, 2)

>>> n = 3
>>> k = 2
>>> w = [2, 5, 2]
>>> v = [2, 3, 1]
>>> solve()
0.75

発展的話題 - 三分探索

三分探索とは擬凸関数 (opens in a new tab)を数値的に最大化・最小化する手法。

「たかだか一つしか極値のない関数 $f$ における極値を探索するアルゴリズム」

(引用: 三分探索を救いたい - @ganyariya (opens in a new tab))

擬凸関数を $f(x)$ 探索範囲を $[l, r]$ とし、範囲の中に極値が一つ含まれているとする。

手順は以下の通り

探索範囲を $3$ 分割する
$1:2$ 、 $2:1$ に内分する点を取る。( $c_{1}=(l \times 2 + r) / 3$ 、 $c_{2}=(l + h \times 2) / 3$ )
$f(c_{1})$ < $f(c_{2})$ の場合 $r=c_{2}$ 、 $f(c_{1})$ > $f(c_{2})$ の場合、 $l=c_{1}$ と探索範囲を更新する

上手順を $r-l$ が任意の精度に小さくなるまで繰り返す。

練習問題

二分探索
- ABC192 D - Base n (opens in a new tab)
三分探索
- ARC054 B - ムーアの法則 (opens in a new tab)
- ABC279 D - Freefall (opens in a new tab)