Implementierung der binären Suche (rekursiv und iterativ) in einem C-Programm

Binäre Suche ist ein Suchalgorithmus, der verwendet wird, um die Position eines Elements (Zielwert) in einem sortierten Array zu finden. Das Array sollte vor der Anwendung der binären Suche sortiert werden.

Die binäre Suche wird auch als logarithmische Suche, binäre Suche und Halbintervallsuche bezeichnet.

Wie es funktioniert

Der binäre Suchalgorithmus vergleicht das zu durchsuchende Element mit dem mittleren Element des Arrays und führt den erforderlichen Prozess basierend auf dem Ergebnis dieses Vergleichs durch.

Fall 1 – Element = mittlerer Wert, finde das Element und gebe den Index zurück.

Fall 2 – Element > mittlerer Wert, Suche nach Element im Subarray, indiziert von Mitte +1 bis n.

Fall 3 – Element

Algorithmus

Parameteranfangswert, Endwert

Step 1 : Find the middle element of array. using ,
middle = initial_value + end_value / 2 ;
Step 2 : If middle = element, return ‘element found’ 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.

Die Implementierungsfunktion des binären Suchalgorithmus verwendet wiederholt aufgerufene Funktionen. Es gibt zwei Arten dieses Aufrufs:

• iterativ
• rekursiv

Ein iterativer Aufrufdurchläuft denselben Codeabschnitt mehrmals.

Rekursiver Aufruf ruft dieselbe Funktion wiederholt auf.

Ein Programm zur Implementierung der binären Suche mithilfe iterativer Aufrufe

Beispiel

Demonstration

#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;
}

Ausgabe

Element found at index : 4

Ein Programm zur Implementierung der binären Suche mithilfe rekursiver Aufrufe

Online. Demonstration

#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;
}

Ausgabe

Element found at index : 3

Das obige ist der detaillierte Inhalt vonImplementierung der binären Suche (rekursiv und iterativ) in einem C-Programm. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!