二分探索法
基本概念
二分探索法は情報科学で広く応用されるアルゴリズムの一つです。その核心的なアイデアは各操作で半分の候補を除外することであり、これにより問題の解を \(\text{log}_2n\)（情報科学では通常 \(\text{log}n\) と表記）の操作回数で見つけることができます。
補足：アルゴリズムの計算量
コンピュータは十分速いかもしれないが、無限速ではない。——『アルゴリズムイントロダクション』
現代のコンピュータの計算速度は非常に高いレベルに達していますが、それが無限に速いわけではありません。ある問題を解決できるアルゴリズムが2つ存在する場合、一方の実行時間が長すぎたりメモリ使用量が大きすぎたりするならば、工学では通常、より優れたもう一方のアルゴリズムが使用されます。計算量はアルゴリズムの効率を測るために生まれました。
情報科学の分野では、一般的に時間計算量と空間計算量が使用されます。これらはアルゴリズムの実行時間やメモリ使用量がデータ规模の増加に伴いどう変化するかを示します。通常は \(O(x)\) 記法を使用して表現します。ここで \(x\) はアルゴリズムが実行する基本操作（加減乗除、メモリアクセスなど）の规模を表します。
簡略化のため、計算量の分析では通常、アルゴリズムの中で最も時間がかかる部分だけを考慮し、定数項は省略します。例えば、アルゴリズムが長さ \(n\) の配列を保存して走査する場合、時間計算量は \(O(n)\)、空間計算量は \(O(n)\) となります。 計算量の詳細については「計算量入門」を参照してください。
基本的な二分探索
二分探索の典型的な応用は、ソートされた配列内での要素検索です。
長さ \(n\) の昇順ソートされた配列 \(a\) と要素 \(x\) が与えられたとき、\(x\) が \(a\) に存在するかどうかを求めよ。
この問題に対する直感的なアプローチは、\(a\) の各要素にアクセスして \(x\) と等しいか確認することです。しかし、この方法では最悪の場合 \(n\) 回の検索が必要であり、時間計算量は \(O(n)\) となり、効率的ではありません。これは、一般的な家庭用コンピュータ（1秒あたり約 \(5\times 10^8\) 回の基本操作を実行）で \(n \le 10^{10}\) のデータを1秒以内に処理できないことを意味します。
配列 \(a\) が昇順ソートされていることに注目すると、検索時にすべての要素をチェックする必要はありません：もし \(a_i < x\) であることがわかれば、\(1\le j < i\) に対してすべて \(a_j < x\) であることがわかります。したがって、これらの要素は条件を満たさないことが直接わかります。
どのようにすれば最も多くのデータを除外できるでしょうか？明らかに、最適な戦略は配列 \(a\) の中央の要素 \(a_{\text{mid}}\) を判断することです。なぜなら、どのような場合でも、少なくとも \(\frac{n-1}{2}\) 個の \(x\) と等しくないデータを除外できるからです。
これにより、二分探索アルゴリズムが導かれます：
long long binary_search(long long x) {
long long ret = -1, left = 1, right = n; // 見つからない場合は-1を返す；a[left] ≤ x ≤ a[right]が既知
while (left <= right) {
long long mid = (left + right) / 2; // 区間の中点
if (a[mid] < x)
left = mid + 1; // [left, mid]を除外
else if (a[mid] > x)
right = mid - 1; // [mid, right]を除外
else { // 答えが見つかった
ret = mid;
break;
}
}
return ret;
}
応用例
二分探索は単なるアルゴリズムではなく、その応用範囲は広く、配列内の要素検索だけに限定されません。
上記の例からわかるように、二分探索を使用するためには、データが単調性を満たしている必要があります。これにより、中点を通じて少なくとも半分の区間を除外できます。ある条件を満たすことを1、満たさないことを0と見なすと、多くの区間の最値を求める問題が単調性を満たすと見なせます。
まとめると、ある問題クラスで二分探索を使用するためには、以下の前提条件があります：
- 答えが固定された区間内にあること；
- 条件を満たす値を直接見つけるのは難しいが、ある値が条件を満たすかどうかを比較的容易に判断できること（さもなければ、二分探索の効率は力まかせの列挙より悪い）；
- 解が区間に対して一定の単調性を持つこと。言い換えれば、\(x\) が条件を満たすなら、\(x+1\) または \(x-1\) も条件を満たすこと（これにより先述の単調性が満たされる）。
例題として、[COCI 2011/2012 #5] EKO / 木を伐る問題を考えてみましょう。
伐木業者のMirkoは\(M\)メートルの木材を切り出す必要があります。Mirkoにとってこれは簡単な仕事ですなぜなら、彼には森を野火のように伐採できる美しい新しい伐木機があるからです。しかし、Mirkoは一列の木しか伐採することが許されていません。 Mirkoの伐木機の動作は次の通りです：Mirkoは高さパラメータ\(H\)（メートル）を設定し、伐木機を高さ\(H\)まで持ち上げ、\(H\)より高い木のすべてを切断します（もちろん、\(H\)メートル以下の部分は変化しません）。Mirkoは切り取られた部分を手に入れます。例えば、一列の木の高さがそれぞれ\(20,15,10,17\)メートルの場合、Mirkoが鋸の刃を\(15\)メートルの高さに設定すると、切断後の木の高さは\(15,15,10,15\)メートルとなり、Mirkoは1本目の木から\(5\)メートル、4本目の木から\(2\)メートル、合計\(7\)メートルの木材を得ます。 Mirkoは生態保護に非常に配慮しているため、過度に木材を伐採することはありません。これが彼が伐木機の鋸の刃をできるだけ高く設定する理由です。Mirkoが少なくとも\(M\)メートルの木材を得ることができる、伐木機の鋸の刃の最大の整数高さ\(H\)を見つけてください。言い換えれば、さらに\(1\)メートル高くすると、彼は\(M\)メートルの木材を得られない場合です。
高さ\(h\)で得られる木材の量は、\(h-1\)で得られる量以上であることがわかります。つまり、高さ\(h\)で得られる木材を\(f(h)\)とすると、この関数は単調非増加を満たします。したがって、この問題は単調性を満たしており、二分探索法で解くことができます。
また、この問題のデータ範囲が大きいため、各\(h\)が条件を満たすかどうかを力まかせにチェックすると時間内に処理できません（後述の「タイムアウト」）。そのため、より優れた二分探索法を使用します。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long tree_count, required_wood;
vector<long long> tree_heights;
long long max_height;
bool is_possible(long long mid) {
long long total_wood = 0;
for (long long height : tree_heights) {
if (height > mid) {
total_wood += height - mid;
}
}
return total_wood >= required_wood;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> tree_count >> required_wood;
tree_heights.resize(tree_count);
for (int i = 0; i < tree_count; i++) {
cin >> tree_heights[i];
max_height = max(max_height, tree_heights[i]);
}
long long left = 0, right = max_height;
while (left < right) {
long long mid = (left + right + 1) / 2;
if (is_possible(mid)) {
left = mid;
} else {
right = mid - 1;
}
}
cout << left << endl;
return 0;
}
このようにして、この問題を効率的に解くことができます。
まとめ
二分探索法は応用範囲の広いアルゴリズムの一つです。この考え方は情報科学だけでなく、他の分野でも非常に有用です。
練習問題
- [NOIP1999 上級グループ] ミサイル迎撃問題
- A-B 数対問題