C言語での二分探索の説明

二分探索法は、ソートされたリストにのみ適用できます。与えられたリストは2つの等しい部分に分けられます。リストでは、キーが中央の要素と比較されています。

次の3つの状況がバイナリ検索で発生する可能性があります-

• 真ん中の要素がキーと一致する場合、検索はここで正常に終了します

• 中央の要素がキーよりも大きい場合、検索は左側のパーティションで続行されます

• 中央の要素がキーよりも低い場合、検索は適切なパーティションで続行されます。

入力（i / p）

ソートされた要素のリスト、キー。

出力（o / p）

• 成功-キーが見つかった場合。
• 失敗-それ以外の場合。

例

以下は二分探索法のCプログラムです-

#include<stdio.h>
int main(){
   int a[50], n, i, key, flag = 0, low, mid, high;
   printf("enter the no: of elements:");
   scanf ("%d",&n);
   printf("enter the elements:");
   for(i=0; i<n; i++)
      scanf( "%d", &a[i]);
   printf("enter a key element:");
   scanf ("%d", &key);
   low = 0;
   high = n-1;
   while (low<= high ){
      mid = (low + high) /2;
      if (a[mid] == key){
         flag = 1;
      break;
   } else {
      if (a[mid] > key)
         high = mid-1;
      else
         low = mid+1;
      }
   }
   if (flag == 1)
      printf ("search is successful");
   else
   printf("search is unsuccessful");
   return 0;
}

出力

上記のプログラムを実行すると、次の結果が得られます-

enter the no: of elements:5
enter the elements:23
45
57
89
90
enter a key element:45
search is successful