二分法(にぶんほう)

二分法(にぶんほう)

  • 正確には二分探索法という。検索したいデータがデータ群の前にあるのか後ろにあるのかを絞る方法。
  • 次のような概念で行う。(下図参照)

二分探索法

  • データの数が多いときに威力を発揮する方法。その代り、データ総数が奇数の場合や前と後ろに検索したいデータがあった場合、同じデータが連続する場合には不向きであるため、細かい設定を必要とする。
  • プログラムを次に示す。

/* 二分法 */

#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:755 t:1 y:1