今回は065 データ構造（配列５）で作成した探索（サーチ）の一種で「二分探索（バイナリーサーチ）」を作ってみます。
まずは考え方から説明します。
前提条件として、データがソートされている必要があります。
※ソートは昇順（小さい順）でも降順（大きい順）でも構いません。
この配列に「５５」があるかどうか調べます。
「線形探索（シーケンシャルサーチ）」では左端から順番に探していましたが、「二分探索」では真ん中から調べます。
しかし、データは１０個あるため、「真ん中」と言われてもどこかわかりません。
そこで「真ん中」を計算するため、以下の式を使います。
（最初の添え字 ＋ 最後の添え字） ÷ ２
上の図に当てはめてみると、
（０ ＋ ９） ÷ ２ ＝ ４．５
となります。
添え字は整数ですから「４．５」は使えませんので、小数点以下を切り捨てた「４」が「真ん中」になります。
※Ｃ言語では、int型での計算は小数点以下切り捨てになりますから簡単ですよね。
では、「真ん中」の数値を見てみましょう。
「４５」ですね。
探しているデータの「５５」よりも小さい値です。
ということは、「４５」以下のデータはこれ以上探す必要が無いということになります。
次に残ったデータのどこを調べるかというと、やはり「真ん中」です。
添え字の５から９までのデータが残っていますので、先ほどの式に当てはめると、
（５ ＋ ９） ÷ ２ ＝ ７
となります。
新しい「真ん中」のデータを見ると「７６」で「５５」よりも大きいです。
ということは、「７６」以上のデータはこれ以上探す必要が無いということになります。
残ったデータから「真ん中」を調べます。
（５ ＋ ６） ÷ ２ ＝ ５ ※小数点以下切り捨て
５番目の添え字の中身は「５５」ですので、探していたデータが見つかりました。
このように、データの「真ん中」を調べていくことで、探索回数をかなり減らすことができます。
今回使ったデータのように１０個の要素があれば、
| 探索方法 | 最大 | 平均 |
|---|---|---|
| 逐次探索 | １０回 | ５回 |
| 二分探索 | ４回 | ３回 |
で探すことが出来ます。
もし、１０００個のデータであれば、
| 探索方法 | 最大 | 平均 |
|---|---|---|
| 逐次探索 | １０００回 | ５００回 |
| 二分探索 | １０回 | ９回 |
となり、差は歴然です。
※ただし、データがソートされている必要があります。
この説明だけではプログラムを書くことは難しいでしょう。
特に「見つからなかった」場合をどのように考えていくのかがはっきりしていません。
そのために、プログラム作成を意識してもう少し細かく説明します。
上の「５５」を探す考え方を、詳細に書いてから「見つからなかった」場合を書きます。
左端の添え字を入れる変数を「left」、右端の添え字を入れる変数を「right」とします。
真ん中の添え字は「center」に入れることにします。
真ん中の添え字を計算する式をＣ言語風に書き換えると、
center = (left + right) / 2;
です。
最初のcenterは「４」になるはずですから、
となります。
dataのcenter番目（Ｃ言語風だとdata[center]）は「４５」ですから、目的の「５５」よりも小さいです。
「４５」以下は不要になり、残ったデータの中から「真ん中」を調べるのですが、データの左端を変更しなければなりません。
現在の「left」は「０」ですが、「４５」までが不要になるので、「left」を「５」に変更します。
「５」という添え字はcenter「４」の右隣ですから、
left = center + 1;
で計算できます。
残ったデータの「真ん中」を再度計算します。
center = (left + right) / 2;
今度の「真ん中」は「７」になります。
「真ん中」のデータは「７６」ですから、目的の「５５」よりも大きいです。
「７６」以上は不要になりますので、データの右端である「right」をcenterの左隣に変更します。
計算式は、
right = center - 1;
となります。
再度、残ったデータの「真ん中」を計算します。
center = (left + right) / 2;
今度の「真ん中」は「５」になり、目的の「５５」を発見出来ました。
次に「見つからなかった」場合の説明をします。
「５６」というデータがあるかどうか調べることにします。
途中までは上の説明と同じ動作をしますので、↓の状況から説明を続けます。
この状況はleftが「５」、rightが「６」、centerが「５」という状況です。
centerが指しているのは「５５」というデータですから、「５６」より小さいです。
「５５」は不要になりますので、leftをcenterの右隣に移動します。
left = center + 1;
新しい「真ん中」を計算すると、
center = (left + right) / 2;
「６」になります。
centerが指しているのは「６７」ですから、目的の「５５」よりも大きいです。
「６７」は不要になり、rightをcenterの左側に移動します。
ここで「left」と「right」が逆転しました。
これが「見つからなかった」状態になります。
では、手順をまとめます。
１．leftに左端の添え字を入れ、rightに右端の添え字を入れる ２．探したいデータを入力する ３．centerを計算する ４．ｄａｔａのcenter番目と目的の数値を比較する ①同じ場合 データは見つかり、終了する ②目的の数値の方が大きい場合 leftをcenterの右隣に変更して３に戻る ③目的の数値の方が小さい場合 rightをcenterの左隣に変更して３に戻る ５．leftとrightが逆転した場合、データは見つからず、終了する |
説明が長くなりましたが、手順をしっかりと考えなければプログラムはまともに動きません。
複雑なプログラムを組むためには手順をはっきりとさせる必要があります。
いきなりプログラムを打ち込むよりも、まずは考え方や手順を明確にすることに力をいれましょう。
それでは、プログラムを作ります。
手順のイメージがはっきりしている方は、自分で作ってみてください。
そうでない方は、少しずつ作って完成させていきます。
元データ↓
<sample program 070-00>
#include <stdio.h>
#define COUNT 10
int main(void)
{
int data[COUNT] = { 9, 12, 23, 32, 45, 55, 67, 76, 88, 98 };
int left;
int right;
int center;
return 0;
}
|
<実行結果１>
探したいデータを入力してください：98 発見！ 続行するには何かキーを押してください・・・
<実行結果２>
探したいデータを入力してください：33 発見できず・・・ 続行するには何かキーを押してください・・・
<実行結果３>
探したいデータを入力してください：12 発見！ 続行するには何かキーを押してください・・・
まずは、手順１を作成します。
１．leftに左端の添え字を入れ、rightに右端の添え字を入れる
<sample program 070-01>
#include <stdio.h>
#define COUNT 10
int main(void)
{
int data[COUNT] = { 9, 12, 23, 32, 45, 55, 67, 76, 88, 98 };
int left;
int right;
int center;
left = 0;
right = COUNT - 1;
return 0;
}
|
次に手順２を作成します。
２．探したいデータを入力する
<sample program 070-02>
#include <stdio.h>
#define COUNT 10
int main(void)
{
int data[COUNT] = { 9, 12, 23, 32, 45, 55, 67, 76, 88, 98 };
int left;
int right;
int center;
int input;
left = 0;
right = COUNT - 1;
printf("探したいデータを入力してください：");
scanf("%d", &input);
return 0;
}
|
手順３を作成します。
３．centerを計算する
<sample program 070-03>
#include <stdio.h>
#define COUNT 10
int main(void)
{
int data[COUNT] = { 9, 12, 23, 32, 45, 55, 67, 76, 88, 98 };
int left;
int right;
int center;
int input;
left = 0;
right = COUNT - 1;
printf("探したいデータを入力してください：");
scanf("%d", &input);
center = (left + right) / 2;
return 0;
}
|
手順４の①を作成します。
４．ｄａｔａのcenter番目と目的の数値を比較する
①同じ場合 データは見つかり、終了する
<sample program 070-04>
#include <stdio.h>
#define COUNT 10
int main(void)
{
int data[COUNT] = { 9, 12, 23, 32, 45, 55, 67, 76, 88, 98 };
int left;
int right;
int center;
int input;
left = 0;
right = COUNT - 1;
printf("探したいデータを入力してください：");
scanf("%d", &input);
center = (left + right) / 2;
if (data[center] == input) {
printf("発見！\n");
}
return 0;
}
|
手順４の②を作成します。
４．ｄａｔａのcenter番目と目的の数値を比較する
②目的の数値の方が大きい場合 leftをcenterの右隣に変更して３に戻る
※手順３に戻るためループを付け加えます。
<sample program 070-05>
#include <stdio.h>
#define COUNT 10
int main(void)
{
int data[COUNT] = { 9, 12, 23, 32, 45, 55, 67, 76, 88, 98 };
int left;
int right;
int center;
int input;
left = 0;
right = COUNT - 1;
printf("探したいデータを入力してください：");
scanf("%d", &input);
for(;;) {
center = (left + right) / 2;
if (data[center] == input) {
printf("発見！\n");
break;
}
if (data[center] < input) {
left = center + 1;
}
}
return 0;
}
|
手順４の③を作成します。
４．ｄａｔａのcenter番目と目的の数値を比較する
③目的の数値の方が小さい場合 rightをcenterの左隣に変更して３に戻る
<sample program 070-06>
#include <stdio.h>
#define COUNT 10
int main(void)
{
int data[COUNT] = { 9, 12, 23, 32, 45, 55, 67, 76, 88, 98 };
int left;
int right;
int center;
int input;
left = 0;
right = COUNT - 1;
printf("探したいデータを入力してください：");
scanf("%d", &input);
for(;;) {
center = (left + right) / 2;
if (data[center] == input) {
printf("発見！\n");
break;
}
if (data[center] < input) {
left = center + 1;
}
if (data[center] > input) {
right = center - 1;
}
}
return 0;
}
|
最後に手順５を作成します。
５．leftとrightが逆転した場合、データは見つからず、終了する
<sample program 070-07>
#include <stdio.h>
#define COUNT 10
int main(void)
{
int data[COUNT] = { 9, 12, 23, 32, 45, 55, 67, 76, 88, 98 };
int left;
int right;
int center;
int input;
left = 0;
right = COUNT - 1;
printf("探したいデータを入力してください：");
scanf("%d", &input);
for(;;) {
center = (left + right) / 2;
if (data[center] == input) {
printf("発見！\n");
break;
}
if (data[center] < input) {
left = center + 1;
}
if (data[center] > input) {
right = center - 1;
}
if (left > right){
printf("発見できず・・・\n");
break;
}
}
return 0;
}
|
<実行結果１>
探したいデータを入力してください：98 発見！ 続行するには何かキーを押してください・・・
<実行結果２>
探したいデータを入力してください：33 発見できず・・・ 続行するには何かキーを押してください・・・
<実行結果３>
探したいデータを入力してください：12 発見！ 続行するには何かキーを押してください・・・
無限ループを使わず、while文で作成したバージョンも書いておきます。
<sample program 070-08>
#include <stdio.h>
#define COUNT 10
int main(void)
{
int data[COUNT] = { 9, 12, 23, 32, 45, 55, 67, 76, 88, 98 };
int left;
int right;
int center;
int input;
left = 0;
right = COUNT - 1;
printf("探したいデータを入力してください：");
scanf("%d", &input);
while (left <= right) {
center = (left + right) / 2;
if (data[center] == input) {
printf("発見！\n");
break;
}
if (data[center] < input) {
left = center + 1;
}
if (data[center] > input) {
right = center - 1;
}
}
if(left > right) {
printf("発見できず・・・\n");
}
return 0;
}
|
<実行結果１>
探したいデータを入力してください：98 発見！ 続行するには何かキーを押してください・・・
<実行結果２>
探したいデータを入力してください：33 発見できず・・・ 続行するには何かキーを押してください・・・
<実行結果３>
探したいデータを入力してください：12 発見！ 続行するには何かキーを押してください・・・
考え方や手順のことをアルゴリズムとも呼びます。
プログラミングで大事なのは言語自体の文法ではなく、このアルゴリズムです。
アルゴリズムを理解していれば、言語が変わってもプログラムは組めます。
配列を使った基本的なアルゴリズムはしっかりと覚えておき、何も見なくても作成出来るようになってください。