C-Programm zur binären Suche (rekursiv und iterativ)

Der binäre Suchalgorithmus ist ein Algorithmus, der auf Vergleichs- und Segmentierungsmechanismen basiert. Der binäre Suchalgorithmus wird auch „Halbrandsuche, logarithmische Suche oder binäre Suche“ genannt. Binärer Suchalgorithmus zum Finden der Position eines Zielwerts in einem sortierten Array. Es vergleicht den Zielwert mit dem mittleren Element des Arrays. Wenn das Element gleich dem Zielelement ist, gibt der Algorithmus den Index des gefundenen Elements zurück. Wenn sie nicht gleich sind, verwendet der Suchalgorithmus die Hälfte des Arrays. Abhängig vom Vergleich der Werte verwendet der Algorithmus die erste Hälfte (wenn der Wert kleiner als die Mitte ist) und die zweite Hälfte (wenn der Wert kleiner als die Mitte ist). die Mitte) und die zweite Hälfte (wenn der Wert größer als die Mitte ist). Machen Sie dasselbe mit der nächsten Hälfte des Arrays.

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

Erklärung

Für unser Array

- vergleichen wir 55 mit dem mittleren Element des Arrays 18, das kleiner als 55 ist, also verwenden wir die zweite Hälfte des Arrays, das Array {24, 45, 55, 99} , die Mitte ist auch 55. Verwenden Sie es, um den Wert des Suchelements zu überprüfen. Und der übereinstimmende Wert, dann geben wir den Index des Werts als 8 zurück.

Wenn das Suchelement kleiner als die Mitte ist, verwenden wir die erste Hälfte und fahren fort, bis das Element in der Mitte des Arrays gefunden wird.

Um die binäre Suche zu implementieren, können wir Code auf zwei Arten schreiben. Diese beiden Möglichkeiten unterscheiden sich nur von der Art und Weise, wie wir die Funktion aufrufen, die das binäre Suchelement überprüft. Dies sind:

• Iteration verwenden

  – Dies bedeutet, dass eine Schleife innerhalb einer Funktion verwendet wird, um die Gleichheit von Zwischenelementen zu überprüfen. < /p>

• Mit

  Bei dieser Methode ruft sich die Funktion immer wieder mit einem anderen Wertesatz auf.

Beispiel

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

Ausgabe

55 is found at Index 8

Beispiel

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

Ausgabe

55 is found at Index 8

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