Heim > Artikel > Backend-Entwicklung > 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.
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
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:
Ein iterativer Aufrufdurchläuft denselben Codeabschnitt mehrmals.
Rekursiver Aufruf ruft dieselbe Funktion wiederholt auf.
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; }
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; }
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!