二分探索の歴史は、1946年まで遡ります。
G. W. Pattersonは完全二分木、すなわち木のサイズが $2^d-1$ ($d$:深さ) のとき、任意の値に対して効率的に探索できることを発見します 1。
完全二分木の性質から、探索する値が左にあるのか右にあるのかで辿っていけば、左右の要素数は同じなので必ず探索サイズはちょうど半分ずつ減っていき、探索回数は必ず深さ $d$ だけになります。
つまり、最悪計算量は $O(\max(d))$ です。
たとえば、上記の図で葉まで辿ったときの「20」「40」「60」「80」の探索は、いずれも2回の探索で済みます。深さが2だからです。
完全二分木でない、すなわちサイズが$2^d-1$でないときは、探索する値によって最悪計算量が変わります。
たとえば上記の図で、葉「11」の探索回数は3回になりますが、葉「2」の探索回数は2回です。
これでは「良いアルゴリズム」とは言えません。
二分探索が今のような形になったのは、それから14年後、1960年のことです。
D. H. Lehmerは「木探索」ではなく「区間探索」をおこなうことで任意のサイズに対して二分探索ができることを示しました2。
int binarySearch(vector<int> &nums, int target) {
int i = 0, j = nums.size() - 1;
while (i <= j) {
int m = (j - i) / 2;
if (nums[m] < target)
i = m + 1;
else if (nums[m] > target)
j = m - 1;
else
return m;
}
return -1;
}
ただし、Lehmerのアイデアも「正しいアルゴリズム」ではあったものの、「正しいインターフェース」ではありませんでした。
たとえば、POSIX標準のbsearchには、以下のように書かれています。
The bsearch() function shall search an array of nel objects, the initial element of which is pointed to by base, for an element that matches the object pointed to by key. The size of each element in the array is specified by width. If the nel argument has the value zero, the comparison function pointed to by compar shall not be called and no match shall be found.
つまり、Lehmerのアルゴリズムでは、その探索値自身がリストにあるのかないのか、それしか分からないということです。
たとえば、
1 3 5 5 5 10 21 37 45
という配列に、20を挿入したいとします。しかし「20」は配列にないため、Lehmerの二分探索では「見つからなかった」という情報しか返却されません。
この場合、配列の先頭から線形探索するしかないですが線形探索は$O(n)$なので、時間がかかります。
また、状況によっては「5」がいくつあるかということも知りたいことがあるかもしれませんが、二分探索は$O(\log n)$なので、二分探索を利用して知ることができれば効率的です。
このように、位置が見つからない場合と、要素が複数ある場合も考慮しながら「正しいインターフェース」を提供する必要があります。
C++のSTLも区間探索ですが、厳密にいえば「境界探索」で、これは「正しいインタフェース」を提供するひとつの解になっています。
たとえば、
1 3 5 5 5 10 21 37 45
の配列に対し、「20」を挿入したいときは、まず配列を20未満かどうかで判定します。
つまり、いま
0 1 2 3 4 5 6 7 8
true true true true true true false false false
です。
このbool配列を$A$、その長さを$N$、先頭位置を$f$とします。
f
↓
0 1 2 3 4 5 6 7 8
true true true true true true false false false
いま、$A[N/2]=A[4]=\text{true}$ なので、境界点は中央より右側にあると考えられます（境界点はtrueとfalseの境目なので）。
したがって、$A[4]$以下を無視して、$f$を先頭位置として更新すると以下のようになります。
f
↓
5 6 7 8
true false false false
この配列の中央は $A[7]=\text{false}$ なので、境界点は中央より左側にあると考えられます。
したがって、$A[7]$以上を無視して、次を考えます。境界点は$f$と中央の間にあるので、$f$は更新しません。
f
↓
5 6
true false
この配列の中央は $A[0]=\text{true}$ なので、境界点は中央より右側にあると考えられます。
したがって、 $A[5]$ 以下を無視して、$f$ を更新すると
f
↓
6
false
となります。
さらに半分を考えると $ n = 0 $ になるので、$f$ の位置を返して終了です。
疑似コードを書くと次のようになります。
Iterator lower_bound(Iterator first, Iterator last, Predicate p) {
n = last - first;
while (n > 0) {
int half = n >> 1;
Iterator mid = first + half;
if (!p(*mid)) {
n = half;
} else {
first = mid + 1;
n = n - (half + 1);
}
}
return first;
}
数学的に書けば、
\exists m \in [f, l) : \left( \forall i \in [f, m) : p(i) \right) \land \left( \forall i \in [m, l) : \neg p(i) \right)
です。
std::lower_bound()を使えば、探索値以上の要素の中で、最も小さい位置を返します。見つからなければ終端を返します。
std::upper_bound()を使えば、探索値より大きい要素の中で、最も小さい位置を返します。見つからなければ終端を返します。
このようにすることで、位置が見つからない場合と、複数見つかった場合も考慮した「正しいインターフェース」を実装することができます。
ちなみに、絶対位置highとlowを持ったアルゴリズムでは、オーバーフローを考慮し、中央の評価を
mid = low + (high - low) / 2
とすることがあります。
意図したものか分かりませんが、上記のC++アルゴリズムはこれをクリアしています。
なぜなら、
Iterator mid = first + half;
ですが、ここでfirstはlowとみなすことができ、halfは中央値の計算そのものです。
したがって、
mid = low + (high - low) / 2
と等価になっています。