目次

二分探索

二分探索は、ソートされた配列や関数から値を効率よく検索するためのアルゴリズムです。 アルゴリズムの詳細については、Wikipediaなどを参照してください。

配列に対する二分探索

ソースコードは次の通り。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// vec から値が val である要素の位置を返す。
// 値が複数あるときは、最も小さな位置を返す。
// 値がなければ、値が val 超である最も小さな位置を返す。
int binsearch_lower_bound(vector<int>& vec, int val) {
  int low = 0;            // 範囲の下限
  int high = vec.size();  // 範囲の上限。解はあれば [low, high] の中に存在する
  while (low < high) {
    int mid = (low + high) / 2;  // 中心点（この実装ではオーバーフローしうる。
                                 // 　厳密には mid=low+(high-low)/2 とすべき）
    int midval = vec[mid];       // 中心での値
    
    // 解の範囲を狭める
    if (midval < val) low = mid + 1;
    else high = mid;
  }
  return low;
}
// 上記の関数のSTLを使った実装。戻り値は全く同じになる
int stl_binsearch_lower_bound(vector<int>& vec, int val) {
  return lower_bound(vec.begin(), vec.end(), val) - vec.begin();
}

// vec から値が val 超である最も小さな要素の位置を返す。
int binsearch_upper_bound(vector<int>& vec, int val) {
  int low = 0;            // 範囲の下限
  int high = vec.size();  // 範囲の上限
  while (low < high) {
    int mid = (low + high) / 2;  // 中心点
    int midval = vec[mid];       // 中心での値
    
    // 解の範囲を狭める（binsearch_lower_bound関数との違いはここだけ）
    if (midval <= val) low = mid + 1;
    else high = mid;
  }
  return low;
}
// 上記の関数のSTLを使った実装。戻り値は全く同じになる
int stl_binsearch_upper_bound(vector<int>& vec, int val) {
  return upper_bound(vec.begin(), vec.end(), val) - vec.begin();
}

int main() {
  int n = 100;
  vector<int> vec(n);
  for (int i = 0; i < n; i++) vec[i] = i * 2;  // 適当な配列を作る

  cout << binsearch_lower_bound(vec, 50)     << endl;  // => 25
  cout << stl_binsearch_lower_bound(vec, 50) << endl;  // => 25
  cout << binsearch_upper_bound(vec, 50)     << endl;  // => 26
  cout << stl_binsearch_upper_bound(vec, 50) << endl;  // => 26
  
  cout << binsearch_lower_bound(vec, 76)     << endl;  // => 38
  cout << binsearch_lower_bound(vec, 51)     << endl;  // => 26
  cout << binsearch_upper_bound(vec, 51)     << endl;  // => 26
  cout << binsearch_lower_bound(vec, 0)      << endl;  // => 0
  cout << binsearch_lower_bound(vec, -1)     << endl;  // => 0
  cout << binsearch_lower_bound(vec, 10000)  << endl;  // => 100

  return 0;
}

上記コードでも記載していますが、配列（正確にはイテレータ）に対する二分探索にはSTLの algorithmヘッダにあるlower_bound関数や upper_bound関数も使えます。

二分探索は考え方は理解しやすいものの、値の範囲の狭め方などコーディングの際にバグを仕込む要因が非常に多いです。 そのため、C++の標準ライブラリの関数を使えるようにするといいでしょう。

配列以外に対する二分探索

プログラムにおいては、二分探索は配列に対して行う場合が多いです。 それに加えて、二分探索は単調な関数、つまり戻り値が引数の値について常に非減少（非増加）である関数にも適用することができます。 蛇足ですが、数値解析の分野では関数に対する二分探索を二分法と言います。

ソースコードは次の通りです。

#include <iostream>
using namespace std;

// 何か単調な関数
double func(double x) {
  return 0.003*x*x*x + 5.5*x - 100; // 0.003x^3 + 5.5x - 100
}

// func(x)=val となるx（の近似値）を[low, high]の範囲内で返す
double binsearch_func(double val, double low, double high) {
  for (int i = 0; i < 100; i++) {   // 100回ループ。これで十分精度がある
    double mid = (low + high) / 2;  // 中心点
    double midval = func(mid);      // 中心での値
    
    // 解の範囲を狭める
    if (midval < val) low = mid;
    else high = mid;
  }
  return low;
}

int main() {
  double low = -10000000;
  double high = 10000000;
  
  cout << binsearch_func(0,         low, high) << endl;  // => 15.9631
  cout << binsearch_func(100,       low, high) << endl;  // => 26.3661
  cout << binsearch_func(100000000, low, high) << endl;  // => 3218.11
  cout << binsearch_func(-10000,    low, high) << endl;  // => -144.777

  return 0;
}

意外なことに、関数に対する二分探索は幅広く応用することができます。 問題をうまく単調関数の形に変換することで、素直に解くと時間がかかりすぎる問題でも効率よく解けることがあります。

具体的な二分探索の適用方法については、プログラミングコンテストチャレンジブックの「値の検索だけじゃない！"二分探索"」や 最強最速アルゴリズマー養成講座：トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター (3/4)を見てください。

問題