二分探索のアルゴリズムを、コードなしでわかりやすく解説。その最大探索回数が [ log_2 n ]+1 である証明も【高校 情報1 探索のプログラム】

高校情報1 では、「探索のプログラミング」として、主に２種類（線形探索と二分探索）を学習します。

そのうち、二分探索 ( binary search ) とはデータの中から、特定の値（数値や文字列）を探索するためのアルゴリズムの一つ。
半分個ずつに分割を繰り返すことによって絞り込んでいく方法です。
データの個数 n が大きくなっても、非常に早く探索できる有効なアルゴリズムです。
ただし「二分探索」の「二分」は、「にぶ」ではなく「にぶん」と読みます。

以下で詳しくみていきましょう。

二分探索とは～ソースコードなしで

例えば、
{ 12, 21, 29, 38, 42, 50, 63, 70 } の８個のデータ。
その中に「63」があるかどうか探索したいというとき。

半分個ずつに分割して「63」の含まれる方を採れば
{ 42, 50, 63, 70 }。これが１回目の操作。
次また、半分個ずつにして「63」を含む方を採り
{ 63, 70 }。これが２回目の操作。
次また半分個ずつで63、1個だけに到達、３回目の操作。

８個→４個→２個→１個となり特定完了。
「半分個ずつに分割して探索する値を含む方を採る ことの繰り返し」が、アルゴリズムの概要です。

２の累乗の指数、\(k\)回で探索完了。確かに今の例、
\(n=8\) では３回で完了していますね。
この例の データ数くらいでは あまり早さ( 回数の少なさ )は実感できませんが、
それがもし データ数\(n=1024(\,=2^{\,10}\,)\) 個であったら、たったの \(k=10\)回目にして１個に絞られるということ。
データの個数が多いほどその早さが分かるでしょう。

実際には \(k=3\)回とか 10回のような、個数２の累乗の 指数の値そのもの だけが探索回数とは限りません。
実際の方法では、データの中央値のときは１回で探索完了 ということさえ あるのです。
またデータ数も、8とか64, 128とか1024のような２の累乗 個 とは限りません。
先ほどの概要はあくまで見易い例でしたが これから、
実際のアルゴリズムを見ていきましょう。

そのとき、データの方にも実は 前提 があって、採ってきてそのままのデータに、すぐアルゴリズムを適用できるかというと そうではないのです。
その点から確認していきましょう。

まず探索をかけるべきデータは、予め整列されてあること

「整列」とは、値の小さい順 (「昇順」) または大きい順 (「降順」) や、文字列であれば「辞書式順序」など、
一定の順序に従って並べておくことです。
要素の重複も、何らかの形で取り除いておきます。
そのようにあらかじめ整えておかないと、二分探索はうまく行えません。

先ほどの例では、
{ 12, 21, 29, 38, 42, 50, 63, 70 } のうちから「63」を探そうと、
{ 12, 21, 29, 38 } と { 42, 50, 63, 70 } とに二分して、「63」を含む方に絞っていきましたが、

もしデータが
{ 12, 63, 42, 50, 29, 21, 70, 38 } のような でたらめな順序だと、
{ 12, 63, 42, 50 } と { 29, 21, 70, 38 } とに二分してみて
「63」を含む方に絞りたくても、
どちらが「63」を含むのかは、結局全部調べない限り、
すぐには判定できず、二分する意味がなくなります。

だから二分探索を適用する前提として、データは予め整列させておくことです。
ここではデータは昇順(小さい順) に並んでいるものと仮定していきましょう。

ついでに、データのような複数の値は、多くのプログラム言語では「配列」とか「リスト」といった
しくみ ( 変数型 ) を構成し、記憶したり利用します。

列挙した値を格納するときに、添字(インデクス) を振っておくのが、配列というしくみ(「型」) なのです。
数列 ( \(a_1 ,\, a_2 ,\,\dotsm\) ) みたいですね。
ただし多くのプログラム言語では、０番から 数え始めるので注意しましょう。

データが昇順に並び 配列に格納されたところで、いよいよアルゴリズムの適用です。
「半分個ずつに分割」と言いましたが。

「半分個ずつに分割」するとは実際‥

「真ん中」で分割しなければなりませんので、「真ん中」の場所をはっきりさせなければいけません。
そのためには、添字(インデクス) を使って計算します。
左端のインデクスを L、右端のを R として、たして２で割れば求まります。
次の例はデータ数\(n=7\) 、
\((L+R)/2\) は \((0+6)/2 = 3\) と求まります。

「二分」、「半分個ずつに分割」と言いましたが、
実際には３分割 なのです。２分割ではありません。
中央のインデクスの値 つまり 中央値に注目するついでに、中央値と探索する値が 等しいかどうかも、ここで判定してしまうのが、早いからです。
もし今のデータから「42」を探索するという場合、たった この１回で探索終了となります。

もしそれが「63」を探索する場合には、どうするでしょうか？
次いで、「探索する値を含む方を採る」・「絞り込む」という操作が必要になります。