二分探索をプログラムにする
この処理をプログラムにしてみましょう。例に掲げた単純な探索処理は、リスト1のようになります。
変数の初期化
探索対象のデータ群は、あらかじめint型の配列“arry”として初期化しておきます。
int arry[] = {1, 3, 5, 8, 12, 16, 19, 24, 26, 31, 35};
配列の範囲を半分ずつ狭めていくため、範囲を表す添字の最小・中間・最大を示す変数を用意します。
int lowid, midid, highid;
探索する値24はint型の変数“target”に保存しておきます。
int target = 24;
添字の初期化
これで前準備が整いました。ここから探索処理に入ります。
まず、添字の最大値と最小値を初期化します。最初は最小値=0、最大値=10として、配列全体を対象とします。
highid = 10;
lowid = 0;
whileループの処理
続いてwhileループに入り、目的の値(24)が見付かるまで『探索対象の範囲を半分に絞っていく』処理を繰り返します。
ループの継続条件は
最小値を示すlowidの値が、最大値を示すhighidの値以下である間
です。
while (lowid <= highid) {
ループの先頭では、探索対象の配列の中間値を変数mididに保存します。
midid = (lowid + highid) / 2;
続くprintf文では、処理の過程を見せるために添字の変化を表示しています。探索処理の本質とは無関係です。
printf("lowid=%d, midid=%d. highid=%d¥n",
lowid, midid, highid) ;
繰り返しと脱出の条件
探索範囲の中間値が探索値(24)と等しくなったら値が見付かったことになるので、そのときにはループを抜けます。
if (arry[midid] == target) {
break;
｝
そうでなく、探索範囲の中間値が探索値(24)より小さい場合は、探索値が中間値より大きい範囲に存在することになるので、対象範囲の最小の添字(lowid)を中間値の添字(midid)にします。これで、探索対象の範囲が現時点での中間から最大の範囲に狭まります。
else if (arry[midid] < target) {
lowid = midid + 1;
そうでなければ、探索範囲の中間値が探索値(24)より大きいことになるため、対象範囲の最大の添字(highid)を中間値の添字(midid)にします。これで、探索対象の範囲が現時点での最小から中間の範囲に狭まります。
else {
highid = midid - 1;
}
こうしてループを繰り返せば、ループを抜けた時点で添字“midid”の示す要素(arry[midid])に探索値が保存されています。
リスト1：11個の配列から24を探す処理～ex5401.c
#include <stdio.h>
/* 探索対象の配列 -- 11個 */
int arry[] = {1, 3, 5, 8, 12, 16, 19, 24, 26, 31, 35};
int main(void)
{
/* 配列の範囲を狭めるための添字 */
int lowid, midid, highid;
/* 探索する値（固定） */
int target = 24;
int i;
printf("探索対象の値 : ");
for (i=0; i<10; i++) {
printf("%2d, ", arry[i]);
}
printf("%2d¥n", arry[10]);
/* 添字の範囲を初期化 */
highid = 10;
lowid = 0;
/* 値が見つかるまで繰り返す */
while (lowid <= highid) {
midid = (lowid + highid) / 2;
/* 添字の変化を表示 */
printf("lowid=%d, midid=%d. highid=%d¥n",
lowid, midid, highid) ;
/* 値が見つかればループを抜ける */
if (arry[midid] == target) {
break;
/* 値の大小を調べて探索範囲を狭める */
} else if (arry[midid] < target) {
lowid = midid + 1;
} else {
highid = midid - 1;
}
}
/* arry[midid] に探索する値 */
printf("値 %d は %d 番目に見つかりました。¥n",
target, midid + 1);
return (0);
}
汎用性を持たせる
この処理にもう少し汎用性を持たせてみましょう。探索対象の値を17個にし、その中からユーザーが探索したい値を入力できるようにしたものがリスト2です。
冒頭で#defineプリプロセッサ指令によって記号定数_YESと_NOを定義していますが、これは値が見付かった場合と見付からなかった場合とでメッセージを切り替えるため、変数isfoundに代入する値です。
探索処理の仕組み自体はex5401.cと変わりません。その他の動作はコメントを参照してください。
リスト2：リスト1(ex5401.c)に汎用性を持たせて探索値を入力できるようにした～ex5402.c
/* ---------------------------------------------------------
ex5402.c -- 二分探索・汎用版
配列にない値を入力すると正しく動作しません。
--------------------------------------------------------- */
#include <stdio.h>
/* 探索結果を示す論理値（intで代用） */
#define _YES 1
#define _NO 0
/* 探索対象の配列 -- 17個 */
int arry[] = {1, 3, 5, 8, 12, 16, 19, 24, 26,
31, 35, 38, 40, 46, 47, 51, 63};
int main(void)
{
int lowid, midid, highid;
int target;
int isfound = _NO;
int i;
printf("探索対象の値 : ¥n ");
for (i=0; i<16; i++) {
printf("%2d, ", arry[i]);
}
printf("%2d¥n", arry[16]);
printf("探索値を入力してください : ");
scanf("%d", &target);
highid = 16;
lowid = 0;
while (lowid <= highid) {
midid = (lowid + highid) / 2;
/* 添字の変化を表示 */
printf("lowid=%d, midid=%d. highid=%d¥n",
lowid, midid, highid) ;
/* 値が見つかればループを抜ける */
if (arry[midid] == target) {
isfound = _YES;
break;
/* 値の大小を調べて探索範囲を狭める */
} else if (arry[midid] < target) {
lowid = midid + 1;
} else {
highid = midid - 1;
}
}
if (isfound == _YES) {
/* arry[midid] にターゲット */
printf("値 %d は %d 番目に見つかりました。¥n",
target, midid + 1);
return (0);
} else {
printf("値 %d は見付かりませんでした。¥n", target);
return (-1);
}
}
＊
今回紹介した二分探索は、データ群が整列されていることが前提となります。整列されていないデータ群を対象とする場合には、以前取り上げた二分探索木の場合のように、元の配列の添字と値とを1組にした構造体を作らなければなりません。
今回は処理の仕組みを分かりやすくするため、整列の過程は割愛しました。
二分探索木では、木構造を生成する過程で整列と対象となるデータ群を半分にする処理を行っています。つまり二分探索木は、二分探索をさらに効率的にしたデータ構造なのです。
アルゴリズムとデータ構造は常に一体、と考えてよいでしょう。
あとがき ～宿題～
冒頭で紹介したパズル「9枚の金貨」では、金貨を3枚の組に分けることで効率的に偽物を発見できました。
では、偽物を含む金貨が10枚あった場合には、どのような手順を採れば効率的に偽物を見つけ出せるでしょう？
100円硬貨9枚（本物の金貨）と10円硬貨1枚（偽の金貨）などを使って、実際に手順をシミュレーションしながら考えてみましょう。
|
|
|
TOP