探索 ―二分探索―
二分探索とは
二分探索は，前回の線形探索に比べると格段に速いアルゴリズムです．とは言え，データが昇順または降順に並んでいるという前提があります．
え～？データが順序良く並んでいる中から，目的のデータを探すなんて状況があるのかいな？
と考える私です．ここが正に素人の浅はかなところです．経験を積んでいないので，様々な状況を頭の中に思い描けないのです．「うん！そういう状況だってあるのだ！」と思うことにして続けましょう．
１ アルゴリズムとしては，決して難しいものではありません．今，1000個の整数データ a[0] ～ a[999] があったとし，a[0] から a[999] に向かって昇順に並んでいるとします．
２ 二つの変数 min と max を考え，それぞれを 0 と 999 とします．データ数が偶数ですから，真ん中の値はありませんが， \(\displaystyle \frac{{\rm min} + {\rm max}}{2}\) 番目，整数値ですから切り捨てて 499 番目の値を中央の値とします．
３ 探索目的の値（これを仮に target と呼ぶことにしましょう）と a[499] を比較します．
target < a[499] ならば，max = 499 とします．
逆にそうでなければ，min = 499 とします．
この時点で，a[min] <= target <= a[max] が成り立ち，探索の幅が半分になります．
４ これを繰り返し，target と \(\displaystyle \frac{{\rm min} + {\rm max}}{2}\) 番目（少数以下は切り捨て）の値とを比較して，探索の幅を２分の１にしていきます．
５ \({\rm max} - {\rm min} = 1\) になったとき，a[min] と a[max] のいずれかが target に等しければ target が配列の中に存在します．逆に，a[min] と a[max] のいずれもが target に一致しなければ target は配列の中に存在しないことになります．
以上が二分探索のアルゴリズムです．
Cording
それでは前回同様に，0 ～ 100 までの 50 個のデータを用意して，探索をしてみましょう．ただし今回は，探索の部分を明確にするため，main 関数には探索部分のみを書き，50 個のデータを作る部分は専用の関数を作ることにします．
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void makeData(int *data);
int main(int argc, char *argv[]) {
int a[50];
int target = atoi(argv[1]);
int max = 49;
min = 0;
makeDate(a);
while (max - min > 1) {
int mid = (max + min) / 2;
(target < a[mid]) ? (max = mid) : (min = mid);
}
if (target != a[min] && target != a[max]) {
printf("リストの中に %d は見つかりませんでした．, target);
} else {
printf("リストの中に %d が見つかりました．, target);
}
return 0;
}
void makeData(int *data) {
srand(time(NULL));
for (int i = 0; i < 50; i++) {
data[i] = rand() % 101;
}
for (int i = 0; i < 50; i++) {
for (int j = 0; j < 49 - i; j++) {
if (data[j] > data[j + 1]) {
int b = data[j];
data[j] = data[j + 1];
data[j + 1] = b;
}
}
}
printf("データリストは [\n");
for (int i = 0; i < 5; i++) {
printf(" ");
for (int j = 0; j < 10; j++) {
printf("%3d ", data[10 * i + j]);
}
printf("\n");
}
print("] です．\n");
}
yossii@penguin:~/C/search$ ./binary 17
データリストは [
0 2 3 4 6 10 11 19 25 27
27 28 29 29 31 33 34 34 34 37
38 42 47 47 51 52 56 59 59 60
62 62 73 73 75 78 79 80 81 82
85 85 89 91 93 96 96 97 98 100
] です
リストの中に 17 は見つかりませんでした．
yossii@penguin:~/C/search$ ./binary 17
データリストは [
1 2 3 4 5 9 10 10 17 17
18 19 21 25 32 33 36 42 44 49
50 53 54 55 56 58 72 73 73 74
77 79 82 83 71 85 86 87 89 90
91 92 95 95 95 98 98 99 100 100
] です
リストの中に 17 が見つかりました．
void makeData(int *data);
main 関数の中でこの関数を使用しています．その場合，main 関数より前に使用する関数を記述する必要があります．main 関数の後ろに記述する際には，このように使用する関数を宣言しておきます．
関数へのポインタ渡し
関数の中で宣言した変数は，その関数の中でしか参照することができません．ところが，ポインタを用いると，変数の格納されているアドレスですから，宣言した関数の外からでも参照することができるようになります．
このプログラムでは，データリストである a[] は main 関数の中で宣言されています．しかし，データを準備する作業は，探索の本質ではないので，makeData 関数で行ってしまおうとしています．
Ｃ言語以外であれば，グローバル変数を利用するところ，Ｃ言語には，ポインタという理解しづらいけれど便利なものがあるのです．
void makeData(int *data) では，引数にポインタすなわちデータの入っているアドレスを受け取っています．main 関数の中で実際に受け取ったのは，makeData(a) ですから，配列 a[] の先頭アドレスです．
つまり，makeData 関数の中の data[] と main 関数の中の a[] は同じものを表していることになります．
このような，データの受け渡しをポインタ渡しといいます．
処理の効率
ここまで全く触れてきませんでしたが，処理の効率を考えてみたいと思います．例えば，\(n\) 個のデータから探索を行う場合，線形探索と二分探索では処理効率にどの程度の違いがあるのでしょうか？
線形探索では，探したいデータがどこにあるかで比較回数が違ってきます．データリストの中に探したいデータがなければ \(n\) 回です．同じ数字が含まれることを考えても，ザックリと期待値 \(\displaystyle \frac{n}{2}\) として大きな違いはなさそうです．
それに対して二分探索では\[n \times \left(\frac{1}{2}\right)^N = 1\]を満たす \(N\) を求めればよいので，\(N = \log_2 n\) となります．
この二つを比べると随分違います．データの個数 \(n\) が大きくなればなるほど著しい違いが生じます．データ解析をお仕事にされている方々は，このようなことを考えながら，どのアルゴリズムを選ぶかを決めなければならないのですね．まぁ，データ解析に限らず，プロのプログラマは皆同じでしょう．大変です．