二分探索のアルゴリズムを、コードなしでわかりやすく解説。その最大探索回数が [ 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」を探索する場合には、どうするでしょうか？
あわせて、探索する値を含む「側」に しぼり込む操作
これを行う必要があります。どうやって？
ー やはり、インデクスで指し示すことで、できます。
「63」は「中央より右」の配列、具体的には「インデクス４～６」に含まれるので、左端のインデクス L を、「０」の代わりに「４」へと変更してあげるのです。
そもそも「『中央より右』の配列の側に含まれる」と判断した 条件は 何か というと、
中央値だった「42」よりも、探索値「63」の方が大きいからです。
データは今、昇順に並んでいましたので、より大きい値ほど右にあるからです。
データが整列されていれば、中央値と探索値の大小 だけ を見ることで、探索値が中央値よりも 右側にあるか 左側にあるか を判断できます。
何百何千のデータ数であっても、そこだけで、判断することができるのです。
同様の考え方で、例えば「38」を探索したいとき。
条件設定から順序だてて述べれば、
このようになります。
中央値に着目し、中央より左側と中央値と中央より右側とに分割して、探索値を含む側にしぼり込む
～ そこまでが、一連の操作 １回分。
この一連の操作を、何回も 繰り返す
その結果、しぼり込まれていった配列の要素の個数が１になったところで、じき探索は完了(「見つかった！」)していくわけです。
今のデータで、「38」を探索する様子と「63」を探索する様子を、同時に１枚に図示すれば、次のようです：
その回で探索する配列のうちの中央値が 探索値と等しい場合には、その回で探索は完了です。
また 中央値以外で、探索する配列が１個の要素だけになった場合は、その次の回で探索は完了です。
次の回で、配列のL\(=\)R なので、その中央のインデクスm とも等しいことになり、その要素自体が中央値となるからです。
「１個だけの要素になったら、探索完了は近い」と考えて正しいですが、必ずその回で完了するわけではなく、あくまでも完了する契機は、探索値が中央値に一致することです。
ただし実は 中央値というか「左中央値」。
以上の例では、データ数\(n=8,\,7\) と見てきましたが、要素をさらに１個落として、\(n=6\) にしてみましょう。
多いデータの個数でももちろん、少ない任意の個数でも、うまくできなければいけません。
まず、中央のインデクスm \(=(L+R)/2\) の計算から。
すると、
実は\(n=8\) でも、よく見れば、起こっていたことです。
こういうときは、次のように決めます：
中央値というか、中央の値が２個ある場合には左の方の値に定めることになるので、「左中央値」と呼ぶべきものです。
両端のインデクスをたして２で割ったとき、割り切れなければ小数を切り捨てます。
「四捨五入」や「切り上げ」ではなくなぜ「切り捨て」かというと、割り切れる場合と分けずに、最も簡単に、プログラム言語に既存の演算子で計算できるからだと考えられます。
数式を少し使うと、中央のインデクスm を求めるためには以後、
割り切れても割り切れなくてもm \(=\)[ \((L+R)/2\) ] 。
数学で出てくるガウス記号。例えば [ 3 ]=3, [ 3.5 ]=3 です。憶えておくとよいでしょう。
ただし負の数ではガウス記号の値は、整数部分を表さないので要注意です。
「半分個ずつに分割」と、前半で説明していたことは便宜上であり、実は語弊あることなのでした。
「情報１」の教科内でも、中学や高校数学１の「データの分析」などでも、中央値(メジアン) を求めたければ、いわば中央の値が２個あるのでそれらをたして２で割る、
今の例でそれをやるならば、(42+50) / 2 = 46 と求めるでしょう。
割り切れなければ、小数のまま出します。
しかし、「データの分析」や統計処理とは異なり、今やっていることは、探索 でした。
この算出した「46」はもともと、探索データにはなかった値。
それを相手にしてみても、もともとあった値の中から探し出すという今の目的にとって、意味はありません。
探索のアルゴリズムで把握する、中央値というか真ん中の値は、統計の「中央値(メジアン)」とは異なります。
今のデータ(\(n=6\))で、「38」を探索する様子と「63」を探索する様子を、同時に１枚に図示すれば、次のようになります：
要素数\(n=2\) の配列の場合、L\(=0\) , R\(=1\) で、
左中央のインデクスm\(=\)[ (L+R)/2 ] は、[ 1/2 ]\(=0\) 。
左側の値がまさに 左中央値になっています。
以上、二分探索のアルゴリズムの流れを、平文でまとめると：
- 「左中央」のインデクスm\(=\) [ (L+R)/ 2 ] の値(「左中央値」)に注目。
- それより左側と「左中央値」と それより右側 に、配列を３分割。
- 2.のうち、探索値を含む側( 不等号で評価 ) の配列に しぼり込む。
- 3.のうち、探索値が「左中央値」に一致していれば、探索完了。
- 探索完了でなければ、1.に戻って繰り返し 次の回目へ。
この繰り返しの回数を数えたものが、探索回数です。
二分探索の探索回数
これまでいくつかのデータの例で、例えば「38」や「63」が探索される様子を見てきました。
ここでさらに詳しく、１つ１つのデータの中の任意の(順位にある) 要素が、それぞれ何回の操作で探索されるか つまり、それぞれの探索回数を見ていきます。
手始めに、少ないデータ数\(n=1,\,2\) の場合から見ていきましょう。