初級者向け アルゴリズムを解説
これからアルゴリズムについて解説をしていきますが、こちらの解説はプログラミング初級者（「最近プログラミングを始めました！！」向けになります。また数回のシリーズに分けてプログラミングで使用されるアルゴリズムを解説していきます。なお、Rubyを使用してコーディングしています。
※このシリーズは「アルゴリズムを、はじめよう（著：伊藤静香）」を参考にしております。
シリーズ(１)： 初級者向け アルゴリズムを解説（１）はこちら
シリーズ(２)： 初級者向け アルゴリズムを解説（２）はこちら
二分探索法(バイナリサーチ)
それでは前回の続きから始めましょう。前回は線形探索法を説明しました。（線形探索法については上記のシリーズ(２)を確認してください。）
今回は探索の中の二分探索法について説明していきます。
二分探索法とは、探索する範囲を半分に絞りながら探索を進めるアルゴリズムです。線形探索法では、配列は整列（昇順又は降順）していなくても探索することが出来ましたが、二分探索法では昇順または降順に整列されていることが探索するための条件となります。
まずはイメージを掴んでいただきたいと思いますので、まず5つの枠に区切られた箱をイメージしてください。その各枠には数字が1つずつ入っていて、その数字は箱から出して見なければわからないようになっています。今回はその箱から1つの数字を探して見たいと思います。今回用意した箱と数字は次の通りです。
[0, 3, 5, 6, 9] （箱が5つの枠に仕切られ、中には0と3と5と6と9が見えないように入っているイメージです。）
探索の流れですが、配列の要素番号の中央値を取得し、その数字が探索したい値か確認します（今回の箱であれば、要素番号2に入っている5が探索したい値か確認）。もし、その数字が探索したい値であれば探索を終了、一致しないのであれば探索範囲を二分します。今回はこの二分するところがポイントで、どうやって探索範囲を半分にするのか、それは探索した際に配列の要素番号の中央値の数字が探索したい値よりも大きいか小さいかで処理が決まります。中央値の数字が探索したい値よりも大きい場合、探索したい数字は配列の前半に存在する可能性があるということなります（探索範囲を0, 3側に絞る）。一方、中央値の数字が探索したい値よりも小さい場合、探索したい値は配列の後半に存在する可能性があるということになります（探索範囲を6, 9側に絞る）。よって、この中央値の値が探索したい値よリも大きいか小さいかで、探索範囲を配列の前半または後半に絞っていくことになります。
今回は6を探すこととし、大まかな手順は次の通りです。
1. 探索するための要素（配列の要素番号の中央値）を取得
2. 取得した要素の数字と探索したい値が一致するか確認
3. 一致した場合、探索終了
4. 一致しない場合、探索する範囲を絞る
5. 絞った要素の中から探索するための要素（中央値）を取得
6. 取得した要素と探索したい数値が一致するか確認...
（１〜４の繰り返し）
それではこれらの内容をコードにしていきましょう。
なお、二分探索法は線形探索法同様、反復構造（同じ処理を繰り返す）になっているため、必ず反復処理を終了させる条件を付けてください。（万が一、探したい数字が箱の中にない場合、プログラムを終了させることができなくなります。）
array = [0, 7, 3, 2 ,1, 6, 9] # ①サンプルとして適当な配列を用意
asc_array = array.sort # ②配列は昇順に並べ替え
head = 0 # ③配列の要素番号の中央値を取得するための変数に要素番号0を代入
tail = array.size.to_i - 1 # ④配列の要素番号の中央値を取得するための変数に要素の末番号を代入（sizeはlengthでも可）
# => ((③ + ④) / 2）).floorで中央値を取得可能
search_number = 6 # ⑤探索する値を6に指定
loop{
center = ((head + tail) / 2).floor # ⑥配列の要素番号の中央値を取得する処理
if head < tail # ⑦反復する処理を終了させる条件
puts "#{search_number}は存在しません。"
break # loopから抜け出す処理(探索終了)
elsif asc_array[center] == search_number # ⑧探したい数字が一致しているか確認する処理
puts "#要素番号{center}に#{search_number}があります。"
break # loopから抜け出す処理(探索終了)
end
# 探索範囲を絞る処理
if asc_array[center] < search_number # ⑨配列の中央値の数字が探索したい数字より小さい場合の処理
head = center + 1
elsif asc_array[center] > search_number # ⑩配列の中央値の数字が探索したい数字より大きい場合の処理
tail = center - 1
end
}
解説（丸付きの番号は上記コードのコメントに該当）
①今回探索に使用する配列になります。適当に数字を7つ入れました。
②二分法は昇順または降順に整列されていることが探索できる条件のため、今回は昇順に整列させました。([0, 1, 2, 4, 6, 7, 9]の順に整列)
③配列の要素番号の中央値を取得するための変数になります。
④配列の要素番号の中央値を取得するための変数になります。
⑤今回は6を探索する数値にしています。試しに他の数値を入れてみてください。
⑥③と④で取得した要素番号を足して2で割ることで要素番号の中央値を取得しています。.floorは配列数が偶数個の場合、中央値に小数0.5が出力されるため.fｌoorで値を四捨五入し、整数にしています。
⑦これは反復を終了させる処理です。
⑧実際に要素番号の中央値が持つ数字と探索したい値を確認する処理になります。
⑨探索した結果、値が一致しなかった場合の処理になります。ここでは中央値の数字が探索したい値よりも小さかった場合、探索したい値が配列の後半にあるということになるので、③で0を代入したheadを中央値+１とすることで探索範囲を配列の後半に絞ることができるようになります。
⑩探索した結果、値が一致しなかった場合の処理になります。ここでは中央値の数字が探索したい値よりも大きかった場合、探索したい値が配列の前半にあるということになるので、④で要素番号の末番号を代入したtailを中央値-１とすることで探索範囲を配列の前半に絞ることができるようになります。
次回予告
今回はここで終了です。次回はハッシュ探索法について説明していきたいと思います。
今回は説明が長ったらしくなり、分かりにくかったと思います。徐々に説明がうまくできるようにしていきたいと思います。