C プログラムでの二分探索 (再帰的および反復的) の実装-C++-php.cn

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

WBOY

リリース： 2023-08-26 14:37:11

転載

964 人が閲覧しました

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

二分探索は、ソートされた配列内の要素 (ターゲット値) の位置を見つけるために使用される検索アルゴリズムです。二分検索を適用する前に、配列をソートする必要があります。

二分探索は、対数探索、二分探索、半区間探索とも呼ばれます。

動作原理

二分探索アルゴリズムは、検索対象の要素と配列の中央の要素を比較し、その比較結果に基づいて必要な処理を実行します。

ケース 1 - 要素 = 中間値、要素を検索し、インデックスを返します。

ケース 2 - 要素 > 中間値、中間 1 から n までのインデックスが付いた部分配列内の要素を検索します。

ケース 3 - 要素

アルゴリズム

パラメータの初期値、終了値

Step 1 : Find the middle element of array. using ,
middle = initial_value + end_value / 2 ;
Step 2 : If middle = element, return &lsquo;element found&rsquo; and index.
Step 3 : if middle > element, call the function with end_value = middle - 1 .
Step 4 : if middle < element, call the function with start_value = middle + 1 .
Step 5 : exit.

ログイン後にコピー

二分探索アルゴリズムの実装関数は繰り返し呼び出し関数を使用します。この呼び出しには 2 つのタイプがあります。

Iteration
Recursion

Iteration call 同じコード部分を複数回ループします。回。

再帰呼び出しとは、同じ関数を繰り返し呼び出すことです。

反復呼び出しを使用してバイナリ検索を実装するプログラム

例

デモ

#include <stdio.h>
int iterativeBinarySearch(int array[], int start_index, int end_index, int element){
   while (start_index <= end_index){
      int middle = start_index + (end_index- start_index )/2;
      if (array[middle] == element)
         return middle;
      if (array[middle] < element)
         start_index = middle + 1;
      else
         end_index = middle - 1;
   }
   return -1;
}
int main(void){
   int array[] = {1, 4, 7, 9, 16, 56, 70};
   int n = 7;
   int element = 16;
   int found_index = iterativeBinarySearch(array, 0, n-1, element);
   if(found_index == -1 ) {
      printf("Element not found in the array ");
   }
   else {
      printf("Element found at index : %d",found_index);
   }
   return 0;
}

ログイン後にコピー

出力

Element found at index : 4

ログイン後にコピー

再帰呼び出しを使用して実装します二分探索プログラム

例

オンラインデモンストレーション

#include <stdio.h>
int recursiveBinarySearch(int array[], int start_index, int end_index, int element){
   if (end_index >= start_index){
      int middle = start_index + (end_index - start_index )/2;
      if (array[middle] == element)
         return middle;
      if (array[middle] > element)
         return recursiveBinarySearch(array, start_index, middle-1, element);
      return recursiveBinarySearch(array, middle+1, end_index, element);
   }
   return -1;
}
int main(void){
   int array[] = {1, 4, 7, 9, 16, 56, 70};
   int n = 7;
   int element = 9;
   int found_index = recursiveBinarySearch(array, 0, n-1, element);
   if(found_index == -1 ) {
      printf("Element not found in the array ");
   }
   else {
      printf("Element found at index : %d",found_index);
   }
   return 0;
}

ログイン後にコピー