sataniC++

C++、競プロ、数学などについて色々考えたりします。

二分法（二分探索）

アルゴリズム アルゴリズム-な

概要

ある条件を満たすものの最大値を求めます。
（ソートされた配列に対してある値を探索したいときも上記の方法で出来ます）


使える状況

概要にもあるとおり、「ある条件を満たすものの最大値」を求めるときは二分法（二分探索）で効率的に探索することが出来ます。


説明

今、条件を満たすものの最大値をNとします。

このとき、ある数iに対して、

  • i\leq Nのとき、iは条件を満たす。
  • i>Nのとき、iは条件を満たさない。

ということが分かります。表にすると次の通りです。

i 0 1 2 ... N-1 N N+1 N+2 ...
条件を満たすか ○ ○ ○ ... ○ ○ × × ...

ここで、探索の範囲を「条件を絶対に満たす値low」から「条件を絶対に満たさない値high」までと限定します。すると、low\leq N < highが成り立ちます。
あとは、この条件を満たすように範囲を狭めていくことで、最終的にNの値を求めることが出来ます。


ただ、その方法として「low+1が条件を満たすか調べ、満たしていたら次はlow+2を調べる」とすると、範囲の大きさによってはかなりの時間を必要としてしまいます（この方法を線形探索といいます）。


それではどうしたら効率よく調べることが出来るかと言うと、この記事タイトルでもある「二分法（二分探索）」を使っていきます。

二分探索では、lowとhighの間の値midを取り、その値が、

  • 条件を満たしていたら、lowにmidを代入
  • 条件を満たしていなかったら、highにmidを代入

します。
そして、またこのときのlowとhighの間の値midを取って…、と繰り返して範囲を狭めていきます。

最終的にlowとhighの差が1となったとき、ちょうどlow以下が条件を満たし、high以上が条件を満たさないことが分かったため、N=lowということがわかります。そのことを以下の表に示します。

before
i 0 1 2 ... N-1 N N+1 N+2 ...
条件を満たすか ○ ○ ○ ... ○ ○ × × ...
lowとhighの位置 low ... high
after
i 0 1 2 ... N-1 N N+1 N+2 ...
条件を満たすか ○ ○ ○ ... ○ ○ × × ...
lowとhighの位置 ... low high ...


計算量に関して、線形探索ではO(high-low)となるところが、二分法（二分探索）ではO(\log_2 (high-low))にまで小さくすることが出来ます。


以上のことをNの位置を仮定した簡単な図で書くと次のようになります。
f:id:satanic0258:20160404181013p:plain
lowからhighまでの範囲がNを含んだままどんどん狭まっていることがわかりますね。


コード(C++)

//要ヘッダ:functional
using ll = long long int;
ll BinarySearch(ll low, ll high, std::function<bool(ll)> check){
    if(high-low==1){
        return low;
    }
    ll mid = (high+low)/2; 
    if(check(mid)){
        return BinarySearch(mid, high, check);
    }else{
        return BinarySearch(low, mid, check);
    }
}

コードの説明

関数を呼び出すときには、

  • 第一引数lowには「条件を絶対に満たす値」
  • 第二引数highには「条件を絶対に満たさない値」
  • 第三引数checkには「条件の関数」

を指定します。

if(check(mid)){
    return BinarySearch(mid, high, check);
}else{
    return BinarySearch(low, mid, check);
}

関数checkでmidについて調べた結果によって、lowかhighのどちらかの値ををmidとして自身の関数を再帰呼び出ししています。

if(high-low==1){
    return low;
}

また、再帰からの脱出の条件は「lowとhighの差が1のとき」なので、このときlowを返すようにしています。


具体例

入力される非負整数inputに対し、\sqrt{input}以下の最大の整数を求める。

「\lfloor \sqrt{input} \rfloorで求められるじゃん！」と思うかもしれませんが、あくまで二分探索の練習なので・・・（簡単でためになる良い問題が思いつかなかった）。

#include <iostream>
#include <functional>
#include <cmath>
#include <iomanip>

using ll = long long int;
ll BinarySearch(ll low, ll high, std::function<bool(ll)> check){
    std::cout << "low|";
    std::cout << std::setw(3) << low;
    std::cout << "--";
    std::cout << std::setw(7) << high;
    std::cout << "|high\n";
    if(high-low==1){
        return low;
    }
    ll mid = (high+low)/2; 
    if(check(mid)){
        return BinarySearch(mid, high, check);
    }else{
        return BinarySearch(low, mid, check);
    }
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    
    ll input;
    std::cin >> input;
    auto check = [=](ll n) -> bool {
        return n*n<=input;
    };

    ll ans = BinarySearch(0, std::pow(2, 20), check);
    std::cout << "answer = " << ans << "\n";

    return 0;
}

（計算中のlowとhighの値を表示するために二分探索の関数の先頭にいろいろ足してます）

入力例とその出力

入力

100000

出力

low|  0--1048576|high
low|  0-- 524288|high
low|  0-- 262144|high
low|  0-- 131072|high
low|  0--  65536|high
low|  0--  32768|high
low|  0--  16384|high
low|  0--   8192|high
low|  0--   4096|high
low|  0--   2048|high
low|  0--   1024|high
low|  0--    512|high
low|256--    512|high
low|256--    384|high
low|256--    320|high
low|288--    320|high
low|304--    320|high
low|312--    320|high
low|316--    320|high
low|316--    318|high
low|316--    317|high
answer = 316

出力結果を見ると、確かにどんどん範囲が狭まっていき、最終的にlowとhighの差が1になっていることがわかります。

答えも、\sqrt{100000}=316.227766\cdots より、条件を満たすものの中での最大値を求めることが出来ていますね。


備考

問題によっては求める最大値が整数とも限らないので、その場合は「lowとhighの差が1」という部分を「差がほぼ0」としたり、各変数の型をdouble型にしたりと、色々工夫が必要だと思います。
そこに関しては、問題を見て適切にコードを書き換えられるようにしておきましょう。

また、冒頭でも述べたように、ソートされた配列について特定の値を調べたいときは、lowを配列の先頭、highを配列の後尾とすることで調べることが出来ます。


ちなみに、midを

mid = (high+low)/2;

としていますが、high+lowがlong long int型（コード中ではll型）の範囲から溢れてしまう可能性があるような場合は、
\displaystyle \begin{align} mid &= \frac{high+low}{2} \\ &= \frac{high-low+2low}{2} \\ &= low+\frac{high-low}{2} \end{align}
より、

mid = low+(high-low)/2;

とすることで解消することが出来ます。


あとがき

実装に関して、上記のコードでは再帰呼び出しをしていますが、whileループで記述しても同様です（その方が速く、メモリも節約できる）。
今回は個人的にイメージしやすい再帰で書いてみました。

文章中では、二分法（二分探索）と書いているところが多いですが、本来二分探索(Binary Search)はソート済みの配列から特定の値を調べるもので、二分法(Bisection method)はある方程式の解を求めるものです。この両者は似て非なるものですが、ある一つの問題に対して、AtCoderの解説スライドでは「二分法」との記載があったり、Twitterでは「二分探索で解いた」という発言も見られるため、両方をまとめて書いておきました。

競プロに関して、この方法はABCのC,D問題、ARCのB問題、yukicoderの★★などでちらほら見かける気がします。
計算量を非常に抑えることが出来るので、ぜひ覚えておきたいアルゴリズムですね。