2-2. 2分探索

　本記事では、2分探索について解説します。

　2分探索（binary search ）とは

　2分探索とは、探索の対象となるデータがすでに整列されていることを前提として、逐次探索よりも効率的に探索を行う方法です。データを比較するたびに、探索範囲を半分に絞り込んでいく（二つに分けていく）ので、2分探索と呼びます。

2分探索の考え方

　数字列 {4, 8, 3, 5, 7} の中から、 "3" を探索していく例を考えます。ただし、2分探索の前提は、対象のデータが整列済みという条件がありましたから、数字列を{3, 4, 5, 7, 8} と並べ替えます。この数字列データが、次のような配列Sに入っているものします。
S[ 1 ] = 3
S[ 2 ] = 4
S[ 3 ] = 5
S[ 4 ] = 7
S[ 5 ] = 8

①. 探索する配列の中央の位置を求めます。
計算式
（探索範囲の先頭の要素番号 + 最期の要素番号）÷ 2
今回の例は、
（1 + 5）÷ 2 = 3
となり、中央の位置を示す要素番号は 3、中央の位置にある配列要素の値（以下、中央の値）は 5 となります。
　なお、割り切れない場合は、小数点以下の切り捨てを行って整数の値にします。

②. ①で求めた中央の値と、探索したい値（以下、探索値）を比較します。
　比較の結果によって、(a)、(b)、(c)に続きます。
(a) 配列中のデータが整列済みなので、「中央の値＜探索値」であれば、中央の値より前半にあるデータは、すべて、中央の値より小さいものばかりです。そして、中央の値よりも探索値の方が大きいことから、「探索値は、探索範囲の前半部分にはない」ということが分かるので、次に探索を行う範囲を後半部分に絞り、①に戻ります。
(b). 「中央の値=探索値」であれば、「探索したい値は見つかった」ということで、探索を終了します。
(c). 「中央の値＞探索値」であれば、(a) と同じ考え方によって「探索したい値は、探索範囲の後半部分にはない」ということが分かるので、次に探索を行う範囲を半分に絞り、①に戻ります。

探す数値が見つからない場合はどうすればよいか

while ( 「見つからない」　かつ　「最後まで調べていない」)
　[探索を行う]
endwhile

（3） 探索を行う部分のアルゴリズム
　次に、「探索を行う」という部分だけに注目して、その内容を思い出してみましょう。
①　探索範囲の中央の位置を決める。
②　中央の値と探索値を比較する。
　(a) 「中央の値＞探索値」：新たな探索範囲を、中央の位置より前半部分とする。
　(b)　「中央の値＝探索値」：「見つかった！」と表示する。
　(c)　「中央の値＜探索値」；新たな探索範囲を、中央の位置より後半部分とする。
この内容を擬似言語で記述します。
　[探索範囲の中央の位置を決める]
if (中央の値 = 探索値)
　[「見つかった！」を表示]
else
　if (中央の値 ＞ 探索値)
　　[新たな探索範囲を前半部分とする]
　else
　　[新たな探索範囲を後半部分とする]
　endif
endif

2分探索のアルゴリズムを段階的に作成すると

ステップ1. 2分探索のアルゴリズムを日本語で記述

while (「見つからない」かつ「最後まで調べていない」)
　[探索範囲の中央の位置を決める]
if (中央の値 = 探索値)
　[「見つかった！」を表示]
else
　if (中央の値 ＞ 探索値)
　　[新たな探索範囲を前半部分とする]
　else
　　[新たな探索範囲を後半部分とする]
　endif
endif
endwhile

ステップ2. 2分探索のアルゴリズムを擬似言語で記述

i ← (L + R) ÷ 2  // 探索範囲の中央の位置を求める
if (A[ i ] = x)  // 中央の値＝探索値
　[「見つかった！」を表示]
else
　if (A[ i ] ＞ x)　// 中央の値＞探索値
　　R ← i - 1　// 新たな探索範囲を前半部分とする
　else
　　L ← i + 1
　endif
endif

ステップ3. 前記アルゴリズムに探索処理の継続条件を繰返し処理を使って表記する

while (A[ i ] ≠ x and L ≦ R)　// 一致しない かつ 探索範囲にデータがある
i ← (L + R) ÷ 2  // 探索範囲の中央の位置を求める
if (A[ i ] = x)  // 中央の値＝探索値
　[「見つかった！」を表示]
else
　if (A[ i ] ＞ x)　// 中央の値＞探索値
　　R ← i - 1　// 新たな探索範囲を前半部分とする
　else
　　L ← i + 1
　endif
 endif
endwhile

ステップ4. 前記初期設定に、変数の初期設定を追記する

L ← 1　// 最初の左端は、配列の先頭
R ← データの数　//最初の右端は、最期のデータ
x ← 探索値　// 探索値も入れておく
i ← (L + R) ÷ 2　// 最初の中央位置
while (A[ i ] ≠ x and L ≦ R)　// 一致しない かつ 探索範囲にデータがある
i ← (L + R) ÷ 2  // 探索範囲の中央の位置を求める
if (A[ i ] = x)  // 中央の値＝探索値
　[「見つかった！」を表示]
else
　if (A[ i ] ＞ x)　// 中央の値＞探索値
　　R ← i - 1　// 新たな探索範囲を前半部分とする
　else
　　L ← i + 1
　endif
 endif
endwhile

以上です。