\(f : \mathbb{N} \to \mathrm{Bool}\) なる関数について、\(f(L) \neq f(R)\) ならば、

• \(f(R)=f(r)\)
• \(f(L)=f(l)\)
• \(r=l+1\)
• \(L \leq l \leq r \leq R\)

となる \(l, r\) のペアが一つ以上存在し、ある一つが次のアルゴリズムで必ず取れる。計算量は \(O(\log(n))\)。

l = L
r = R
while (r - l > 1):
    m = (r + l) // 2
    if f(m) == f(L):
        l = m
    else:
        r = m

特に、インタラクティブ問題で鍵になることが多い。
長さ2N（Nは奇数）の+1/-1の列aが与えられる。+1/-1はN個ずつある。f(l) は区間 [l,l+N) の和が負なら True, 正ならば False を返す。[l, l+N-1)の和が0, a[l] != a[r] となるような l を求めよ。

a[0..i)の値の種類数をO(1)で得られる。a[0]以外が分かっている。a[0]と等しい箇所が他に必ず存在する。a[0]を特定せよ。

\(f : \mathbb{N} \to \mathrm{Bool}\) なる関数について、\(f(L) \neq f(R)\) ならば、

• \(f(R)=f(r)\)
• \(f(L)=f(l)\)
• \(r=l+1\)
• \(L \leq l \leq r \leq R\)

となる \(l, r\) のペアが一つ以上存在し、ある一つが次のアルゴリズムで必ず取れる。計算量は \(O(\log(n))\)。

l = L
r = R
while (r - l > 1):
    m = (r + l) // 2
    if f(m) == f(L):
        l = m
    else:
        r = m

特に、インタラクティブ問題で鍵になることが多い。

• 長さ2N（Nは奇数）の+1/-1の列aが与えられる。+1/-1はN個ずつある。f(l) は区間 [l,l+N) の和が負なら True, 正ならば False を返す。[l, l+N-1)の和が0, a[l] \neq a[r] となるような l を求めよ（ddcc2020_qual_e）。
• a[0..i)の値の種類数をO(1)で得られる。a[0]以外が分かっている。a[0]と等しい箇所が他に必ず存在する。a[0]を特定せよ。

\(f\) を \(\mathrm{Bool}\) への関数ではなく \(\mathbb{Z}/\mathbb{2Z}\) への関数だと思うと \(f(R) \neq f(L)\) は
\begin{align}
&f(L) \neq f(R) \bmod 2 \\
\Leftrightarrow &f(R) \pm f(L) = 1 \bmod 2
\end{align}
となる。例えば、\(f(i)=g(i)+i\) とすると、\(g(R)-g(L)+(R-L) = 1 \bmod 2\)となるがこれは次のような問題に使える。

判定問題にすることで実装の簡略化

もっと良い計算量で解けるのに、あえて二分探索で判定問題に帰着し、実装を簡略化するテクニックがある。