二分探索法(バイナリサーチ)とは？
あらかじめソートされた配列を前半と後半に区切る処理を繰り返すことで探索範囲を狭め、
目的の結果にたどり着くアルゴリズムです
配列のインデックス（最初・最後）を元に割り出した
真ん中の配列の中身の数値と対象の数値を比較し、探索範囲を定めます
整数型の配列の設定
たとえば、インデックス数「7」の配列を用意します
int[] array = {10,12,19,20,28,29,40};
としましょう
あらかじめ昇順にソートしてあります
変数の設定
探したい数値を格納する変数「target」、さらに、配列のインデックスを格納する変数「head」「tail」も用意します
//例：探したい数値は19
int target = 19;
//初期状態では配列の最初のインデックスarray[0]
int head = 0;
// 初期状態では配列の最後のインデックスarray[tail] 、つまり「6」が入る
int tail = array.length - 1;
平均値を求める
処理する配列を二等分するには平均を用い、配列のインデックスに代入します
平均値を格納する変数「middle」を設定します
int middle = (head + tail) / 2;
※ここではJavaを例にしています
middleを整数型としているので、「暗黙の型変換」が行われます
もしhead + tailが奇数の場合、つまり平均値が小数を含んでいるのなら、Javaの仕様により小数点以下は切り捨てられますが、使用する言語によってはうまく切り捨てられないかもしれません
正解の場合
targetがmiddleと一致しているなら、「middle番目のインデックスにあります」と出力しましょう
///targetがmiddleと一致なら
array[middle] == target;
//「middle + "番目のインデックスにあります"」と出力
System.out.println(middle + "番目のインデックスにあります");
サーチする
実はここからが本番です
たまたま求めたい数値「19」が配列のど真ん中にあり、「target」が収められたインデックスの数値と配列のインデックスの平均値「middle」が一致していればしめたものですが・・・
だんだんサーチする範囲を狭めていきます
array[middle] < target
もし、最初に二分した配列のインデックスの中身がtargetを上回っていれば、middleより小さいインデックスの配列は
もはや探す必要がありません
配列の中身は昇順なので、middleより小さい配列に
19以上の数が入っていることはありえないからです
なので、後半をサーチします
逆に最初に二分した配列のインデックスの中身が19を上回っていれば、
middle未満のインデックスにあるはずです
前半をサーチします
真であれば、対象の配列の最初のインデックスheadにmiddle + 1を代入、
偽であれば配列の最後のインデックスtailにmiddle - 1を代入していきます
if(array[middle] < target){
head = middle + 1;
} else {
tail = middle - 1;
}
middleが「target = 19」と一致するまで、新たに変数middleの更新
int middle = (head + tail) / 2;と
上記の配列の分割処理
if(array[middle] < target){
head = middle + 1;
} else {
tail = middle - 1;
}
の2つを続けます
while文を使うと良いでしょう
すると、array[middle] = targetに行き着きます
System.out.println(middle + "番目のインデックスにあります");
2番目のインデックスにあります
見つからないとき
配列arrayにtargetの数値がないときはおかしな現象が起こります
int[] array = {10,12,19,20,28,29,40};
int target = 17; //arrayにない数値！
一回目のサーチ
int middle = (head + tail) / 2;
/*middleは(0 + 6) / 2 = 3
array[3]は20なのでtargetである19より大きいので、else if文が適用される*/
if (array[middle] == target) {
//このif文はスルー
System.out.println(middle + "番目のインデックスにあります");
} else if (array[middle] < target) {
//後半をサーチし始めるので、headに4が入る
head = middle + 1
} else {
tail = middle - 1;
}
head = 4
tail = 6
middle = 3
二回目のサーチ
int middle = (head + tail) / 2;
/*middleは(4 + 6) / 2 = 5
array[3]は20なのでtargetである19より大きいので、else if文が適用される*/
} else if (array[middle] < target) {
//後半をサーチし始めるので、headに5が入る
head = middle + 1;
} else {
tail = middle - 1;
}
/*※この時点での変数の数値
middle = 5
head = 5
tail = 4*/
最後のインデックスtail = 4が最初のインデックスhead = 5より小さいという奇妙なことになります
while文の条件式にhead <= tailを設定しましょう
while文のスコープの外に
if(head > tail){
System.out.println("対象が見つかりません");
}
と書いておきます
例(Java)
public class Main {
public static void main(String[] args) {
int[] array = {10,12,19,20,28,29,40}; //配列
/*下記binarySearchメソッドに渡す引数と配列
サーチ対象の変数「target = 19」、配列名「array」
*/
binarySearch(19,array);
}
public static void binarySearch(int target,int[] array) {
int head = 0; //最初のインデックス
int tail = array.length - 1; //最後のインデックス
//あらかじめ配列の長さから1を引いてある理由は、インデックスが0から始まるため
//「head <= tail」という条件を満たすときに、while式のスコープ内の処理を実行
while (head <= tail) {
//平均値の計算
int middle = (head + tail) / 2;
if (array[middle] == target) {
//インデックスを出力
System.out.println(middle + "番目のインデックスにあります");
//このbreak文を用いてwhile式から抜け出さないと、無限ループの可能性大
break;
} else if (array[middle] < target) {
//array[middle]がtargetを下回っていれば、配列の後半をサーチ
head = middle + 1;
} else {
//そうでなければ、配列の前半をサーチ
tail = middle - 1;
}
//対象が見つからなければ、最初のインデックスが最後のインデックスより大きくなる現象が起きるため
if(head > tail){
System.out.println("対象が見つかりません");
}
}
}
}