二分法(にぶんほう)
二分法(にぶんほう)
- 正確には二分探索法という。検索したいデータがデータ群の前にあるのか後ろにあるのかを絞る方法。
- 次のような概念で行う。(下図参照)
- データの数が多いときに威力を発揮する方法。その代り、データ総数が奇数の場合や前と後ろに検索したいデータがあった場合、同じデータが連続する場合には不向きであるため、細かい設定を必要とする。
- プログラムを次に示す。
/* 二分法 */
#include<stdio.h>
#define N 10
void b_search(int n_data[N], int s_no);
main()
{
int n_data[N]={2,5,3,4,1,9,10,6,7,8};
int s_no=0;
printf("検索したい数値を入力してください\n");
scanf("%d",&s_no);
b_search(n_data, s_no);
}
/* 二分法のアルゴリズム */
void b_search(int n_data[N], int s_no)
{
int pos1=0, pos2=0;
int i, j;
int flg=0;
/* 検索したいデータが存在するかをチェック */
for(i=0;i<N;i++)
{
/* 検索したいデータがない場合 */
if(s_no!=n_data[i] && i==N-1)
{
flg=0;
}
if(s_no==n_data[i])
{
/* 検索したいデータが前にある場合 */
if(i<=4)
{
pos1=i+1;
flg=1;
break;
}
/* 検索したいデータが後ろにある場合 */
else
{
pos1=i;
flg=2;
break;
}
}
}
/* 検索したいデータが前にある場合 */
if(flg==1)
{
for(j=0;j<pos1;j++)
{
if(s_no==n_data[j])
{
pos2=j+1;
break;
}
}
printf("%dは、%d番目に存在します\n",s_no, pos2);
}
/* 検索したいデータが後ろにある場合 */
else if(flg==2)
{
for(j=pos1;j<N;j++)
{
if(s_no==n_data[j])
{
pos2=j+1;
break;
}
}
printf("%dは、%d番目に存在します\n",s_no, pos2);
}
/* 検索したいデータがない場合 */
else
{
printf("%dは存在しません\n",s_no);
}
}
a:2583 t:2 y:0