二分探索用の C プログラム (再帰的および反復的)

二分探索アルゴリズムは、比較および分割メカニズムに基づいたアルゴリズムです。二分探索アルゴリズムは、半区間探索、対数探索、または二分探索とも呼ばれます。ソートされた配列内のターゲット値の位置を見つけるための二分探索アルゴリズム。ターゲット値と配列の中央の要素を比較します。要素がターゲット要素と等しい場合、アルゴリズム は見つかった要素のインデックス を返します。それらが等しくない場合、検索アルゴリズムは値の比較に応じて配列の半分を使用し、アルゴリズムは前半 (値が中央より小さい場合) と後半 (値が中央より小さい場合) を使用します。中央）と後半（値が中央より大きい場合）。配列の次の半分でも同じことを行います。

Input:
A[] = {0,2,6,11,12,18,34,45,55,99}
n=55
Output:
55 at Index = 8

説明

配列 -

では、55を配列の中央の要素18と比較します。これは55未満であるため、配列を使用します。配列の後半は {24, 45, 55, 99} で、真ん中にも 55 があります。検索要素の値を確認するために使用します。一致した値の場合、値のインデックスを 8 として返します。

検索要素が中央よりも小さい場合は、前半を使用して要素が配列の中央で見つかるまで続行します。

二分探索を実装するには、2 つの方法でコードを作成できます。これら 2 つの方法は、二分探索要素をチェックする関数を呼び出す方法とのみ異なります。

• 繰り返しを使用する - これは、関数内でループを使用して中間要素の同等性をチェックすることを意味します。

• 使用法 このメソッドでは、関数は異なる値のセットを使用してそれ自体を何度も呼び出します。

例

#include<stdio.h>
int iterativeBsearch(int A[], int size, int element);
int main() {
   int A[] = {0,12,6,12,12,18,34,45,55,99};
   int n=55;
   printf("%d is found at Index %d </p><p>",n,iterativeBsearch(A,10,n));
   return 0;
}
int iterativeBsearch(int A[], int size, int element) {
   int start = 0;
   int end = size-1;
   while(start<=end) {
      int mid = (start+end)/2;
      if( A[mid] == element) {
         return mid;
      } else if( element < A[mid] ) {
         end = mid-1;
      } else {
         start = mid+1;
      }
   }
   return -1;
}

出力

55 is found at Index 8

例

#include<stdio.h>
int RecursiveBsearch(int A[], int start, int end, int element) {
   if(start>end) return -1;
      int mid = (start+end)/2;
   if( A[mid] == element ) return mid;
   else if( element < A[mid] )
      RecursiveBsearch(A, start, mid-1, element);
   else
      RecursiveBsearch(A, mid+1, end, element);
}
int main() {
   int A[] = {0,2,6,11,12,18,34,45,55,99};
   int n=55;
   printf("%d is found at Index %d </p><p>",n,RecursiveBsearch(A,0,9,n));
   return 0;
}

出力

55 is found at Index 8

以上が二分探索用の C プログラム (再帰的および反復的)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。