広告
↓発売日：2018年09月22日↓
 |
新品価格 |
２分探索法
今回は２分探索法をやります。
あらかじめ昇順か降順に整列された配列など複数の要素に対して、２分割を繰り返す事で探索する範囲を狭めながら対象物を見つける探索法でバイナリサーチともいいます。
昇順か降順に整列された状態でなければ使えないので注意です。
普通に２分探索法
#include <stdio.h>
int main(){
int ary[10] = {5,7,13,18,27,32,38,52,60,78};
int target = 52;
int head = 0;
int tail = 9;
int center = (head + tail) / 2;
int j = 0;
while(1){
if(ary[center] == target || head > tail){
break;
}
else if(ary[center] < target){
head = center + 1;
}
else{
tail = center - 1;
}
center = (head + tail) / 2;
}
printf("配列の内容\n");
for(j=0;j<10;j++){
printf("[%d]",ary[j]);
}
printf("\n\n探す数字 = %d\n\n",target);
if(head > tail){
printf("見つかりませんでした！\n");
}
else{
printf("添え字番号%d番目で見つかりました！\n",center);
}
return 0;
}
■実行結果■
昇順(小さい順)に整列された配列「ary」から対象となる数字、今回は数字の「52」を探索します。
まずは探す対象を決めるのと、必要な変数を用意します。
int target = 52; int head = 0; int tail = 9; int center = (head + tail) / 2;
探す対象は変数「target」に、探索する範囲の先頭の添え字を保存する変数「head」、同じく末尾の添え字を保存する変数「tail」、そして中央の添え字を保存する変数「center」を用意しました。
「center」には先頭の添え字「head」と末尾の添え字「tail」の中間を計算してその結果を保存しておきます。
それでは２分探索していきます。
while(1){
if(ary[center] == target || head > tail){
break;
}
else if(ary[center] < target){
head = center + 1;
}
else{
tail = center - 1;
}
center = (head + tail) / 2;
}
あらためて２分探索の手順を簡単に説明すると、探索する範囲の中間、さきほどの「center」の値を調べて一致すればそこで探索終了、一致しない場合はその値と目標の値の大小を比べる事によって探索範囲を狭めていくというような手順になります。
一つ一つ見ていきましょう。
中間の値と比べる
if(ary[center] == target || head > tail){
break;
}
中間の値を調べて目標の数と比較します。
「ary[center] == target」こちらが中間の値と目標の値との比較なりますね。
こちらの条件が一致した場合はそこが目標の数字という事なので「break」でループを抜けます。
もう一つの「head > tail」こちらは「head」が「tail」を上回った場合という事ですね。
これは少しずつ範囲を狭めていった結果最後まで目標の数字が見つからなかった場合はこの状態になるので、この場合も「break」でループを抜けます。
中央の数字 < 目標の数字
else if(ary[center] < target){
head = center + 1;
}
この場合は中央より下の部分に目標の数字は存在しないという事になるので先頭の添え字を保存する「head」に中央の値を一つ先に進めた値を保存しなおします。
配列の内容が降順(大きい順)の場合はこちらの部分の不等号を
else if(ary[center] < target)
↓
else if(ary[center] > target)
逆にします。
中央の数字 > 目標の数字
else{
tail = center - 1;
}
先ほどの逆のパターンですね。
同じように今度は中央より上の部分に目標の数字は存在しないという事になるので末尾の添え字を保存する「tail」に中央の値から一つ引いた値を保存しなおします。
center = (head + tail) / 2;
あとは再び「center」に先頭の添え字「head」と末尾の添え字「tail」の中間を計算してその結果を保存しなおす、という作業を繰り返します。
これで普通の２分探索法は完了です。
２分探索法関数
#include <stdio.h>
int my_binary(int* ,int,int,int);
int main(){
int ary[10] = {5,7,13,18,27,32,38,52,60,78};
int target = 52;
int result = 0;
int j = 0;
result = my_binary(ary,target,0,9);
printf("配列の内容\n");
for(j=0;j<10;j++){
printf("[%d]",ary[j]);
}
printf("\n\n探す数字 = %d\n\n",target);
if(result == -1){
printf("見つかりませんでした！\n");
}
else{
printf("添え字番号%d番目で見つかりました！\n",result);
}
return 0;
}
int my_binary(int* ary,int target,int index_head,int index_tail){
int center = (index_head + index_tail) / 2;
while(1){
if(*(ary + center) == target || index_head > index_tail){
break;
}
else if(*(ary + center) < target){
index_head = center + 1;
}
else{
index_tail = center - 1;
}
center = (index_head + index_tail) / 2;
}
if(index_head > index_tail){
return -1;
}
else{
return center;
}
}
■実行結果■
２分探索法の関数を作ります。
int my_binary(int* ary,int target,int index_head,int index_tail){
int center = (index_head + index_tail) / 2;
while(1){
if(*(ary + center) == target || index_head > index_tail){
break;
}
else if(*(ary + center) < target){
index_head = center + 1;
}
else{
index_tail = center - 1;
}
center = (index_head + index_tail) / 2;
}
if(index_head > index_tail){
return -1;
}
else{
return center;
}
}
ここで必要な情報は対象を探す配列、探す対象、探す範囲の先頭・末尾なので
int my_binary(int* ary,int target,int index_head,int index_tail)
引数はこちらになります。
あとは同じように２分割を繰り返す事で探索する範囲を狭めながら対象物を見つけていきます。
配列が引数の場合はその先頭アドレスが渡されるのでそのまま
*ary
こちらが最初の要素となり、その後の要素はそこにアドレス演算をするようなカタチで求めます。
ary[2]
↓
*(ary + 2)
配列などを渡している時はバッファオーバーしないように配列サイズの監視も重要です。
広告
構造体配列に２分探索法
#include <stdio.h>
struct STUDENT{
char name[128];
int score;
};
int my_binary2(struct STUDENT* ,int,int,int);
int main(){
int result = 0;
int target = 52;
int j = 0;
struct STUDENT student[10] = {
{"tanaka",5},
{"suzuki",7},
{"satou",13},
{"saitou",18},
{"watanabe",27},
{"aoki",32},
{"inoue",38},
{"koike",52},
{"wada",60},
{"ueno",78},
};
result = my_binary2(student,target,0,9);
printf("配列の内容\n");
for(j=0;j<10;j++){
printf("名前 %s:得点 %d\n",student[j].name,student[j].score);
}
printf("\n探す対象 = %d\n\n",target);
if(result == -1){
printf("見つかりませんでした！\n");
}
else{
printf("添え字番号%d番目で見つかりました！\n",result);
printf("名前 %s:得点 %d\n",student[result].name,student[result].score);
}
return 0;
}
int my_binary2(struct STUDENT* ary,int target,int index_head,int index_tail){
int center = (index_head + index_tail) / 2;
while(1){
if((ary + center)->score == target || index_head > index_tail){
break;
}
else if((ary + center)->score < target){
index_head = center + 1;
}
else{
index_tail = center - 1;
}
center = (index_head + index_tail) / 2;
}
if(index_head > index_tail){
return -1;
}
else{
return center;
}
}
■実行結果■
より実用的なプログラムにおいては構造体の特定の要素を探索する事もあるかもしれません。
struct STUDENT{
char name[128];
int score;
};
生徒の名簿からある特定の点数を２分探索法を用いて探索しそのデータを表示します。
int my_binary2(struct STUDENT* ary,int target,int index_head,int index_tail){
int center = (index_head + index_tail) / 2;
while(1){
if((ary + center)->score == target || index_head > index_tail){
break;
}
else if((ary + center)->score < target){
index_head = center + 1;
}
else{
index_tail = center - 1;
}
center = (index_head + index_tail) / 2;
}
if(index_head > index_tail){
return -1;
}
else{
return center;
}
}
今回は構造体の配列を渡すので引数は
int my_binary2(struct STUDENT* ary,int target,int index_head,int index_tail){
}
構造体の配列の先頭アドレスを受け取る為のポインタと探す対象と探す範囲の先頭・末尾になりますね。
あとは同じように２分割を繰り返す事で探索する範囲を狭めながら対象物を見つけていきます。
int center = (index_head + index_tail) / 2;
while(1){
if((ary + center)->score == target || index_head > index_tail){
break;
}
else if((ary + center)->score < target){
index_head = center + 1;
}
else{
index_tail = center - 1;
}
center = (index_head + index_tail) / 2;
}
この時に構造体の各メンバにアクセスするには
(ary + center)->score
ポインタで受け取っているのでアロー演算子になる事に注意です！
広告
↓発売日：2016年02月29日↓
 |
12歳からはじめる ゼロからのC言語 ゲームプログラミング教室 新品価格 |
↓発売日：2018年06月22日↓
 |
新品価格 |
↓発売日：2018年03月09日↓
 |
新品価格 |
↓発売日：2017年06月14日↓
 |
新品価格 |
↓発売日：2018年05月21日↓
 |
新品価格 |
↓発売日：2017年12月07日↓
 |
新品価格 |
↓発売日：2017年02月08日↓
 |
新・明解C言語で学ぶアルゴリズムとデータ構造 (明解シリーズ) 新品価格 |
↓発売日：2017年09月26日↓
 |
新品価格 |
