logo

TechCodeview

Binärer Suchalgorithmus – Iterative und rekursive Implementierung

Binäre Suche Algorithmus ist ein Suchalgorithmus Wird in einem sortierten Array verwendet nach wiederholtes Teilen des Suchintervalls in zwei Hälften . Die Idee der binären Suche besteht darin, die Information zu nutzen, dass das Array sortiert ist, und die Zeitkomplexität auf O(log N) zu reduzieren.

Binäre Suche ist ein Suchalgorithmus, der verwendet wird, um die Position eines Zielwerts innerhalb eines zu finden sortiert Array. Dabei wird das Suchintervall wiederholt halbiert, bis der Zielwert gefunden wird oder das Intervall leer ist. Das Suchintervall wird halbiert, indem das Zielelement mit dem Mittelwert des Suchraums verglichen wird.

alles ersetzen

So wenden Sie den binären Suchalgorithmus an:



  • Die Datenstruktur muss sortiert sein.
  • Der Zugriff auf jedes Element der Datenstruktur nimmt eine konstante Zeit in Anspruch.

Binärer Suchalgorithmus:

In diesem Algorithmus gilt

  • Teilen Sie den Suchraum durch in zwei Hälften Finden des mittleren Index Mitte .

Finden der mittleren Indexmitte im binären Suchalgorithmus

  • Vergleichen Sie das mittlere Element des Suchraums mit dem Schlüssel.
  • Wird der Schlüssel im mittleren Element gefunden, wird der Vorgang beendet.
  • Wenn der Schlüssel im mittleren Element nicht gefunden wird, wählen Sie aus, welche Hälfte als nächster Suchraum verwendet werden soll.
    • Wenn der Schlüssel kleiner als das mittlere Element ist, wird die linke Seite für die nächste Suche verwendet.
    • Wenn der Schlüssel größer als das mittlere Element ist, wird die rechte Seite für die nächste Suche verwendet.
  • Dieser Vorgang wird fortgesetzt, bis der Schlüssel gefunden wird oder der gesamte Suchraum erschöpft ist.

Wie funktioniert der binäre Suchalgorithmus?

Um die Funktionsweise der binären Suche zu verstehen, betrachten Sie die folgende Abbildung:

Betrachten Sie ein Array arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} , und das Ziel = 23 .

Erster Schritt: Berechnen Sie die Mitte und vergleichen Sie das mittlere Element mit dem Schlüssel. Wenn der Schlüssel kleiner als das mittlere Element ist, verschieben Sie ihn nach links. Wenn er größer als das mittlere Element ist, verschieben Sie den Suchraum nach rechts.

  • Der Schlüssel (d. h. 23) ist größer als das aktuelle Mittelelement (d. h. 16). Der Suchraum verschiebt sich nach rechts.

Binärer Suchalgorithmus: Schlüssel mit 16 vergleichen

  • Der Schlüssel liegt unter der aktuellen Mitte 56. Der Suchraum wird nach links verschoben.

Binärer Suchalgorithmus: Schlüssel mit 56 vergleichen

Zweiter Schritt: Wenn der Schlüssel mit dem Wert des mittleren Elements übereinstimmt, wird das Element gefunden und die Suche gestoppt.

Binärer Suchalgorithmus: Schlüsselübereinstimmungen mit Mitte

Empfohlene Praxis für die binäre Suche Probieren Sie es aus!

Der Binärer Suchalgorithmus kann auf die folgenden zwei Arten implementiert werden

  • Iterativer binärer Suchalgorithmus
  • Rekursiver binärer Suchalgorithmus

Nachfolgend sind die Pseudocodes für die Ansätze aufgeführt.

Iterativer binärer Suchalgorithmus:

Hier verwenden wir eine While-Schleife, um den Prozess des Schlüsselvergleichs und der Aufteilung des Suchraums in zwei Hälften fortzusetzen.

Implementierung des iterativen binären Suchalgorithmus:

C++ 
// C++ program to implement iterative Binary Search #include  using namespace std; // An iterative binary search function. int binarySearch(int arr[], int low, int high, int x) {  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was not present  return -1; } // Driver code int main(void) {  int arr[] = { 2, 3, 4, 10, 40 };  int x = 10;  int n = sizeof(arr) / sizeof(arr[0]);  int result = binarySearch(arr, 0, n - 1, x);  (result == -1)  ? cout << 'Element is not present in array'  : cout << 'Element is present at index ' << result;  return 0; }>
C 
// C program to implement iterative Binary Search #include  // An iterative binary search function. int binarySearch(int arr[], int low, int high, int x) {  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was not present  return -1; } // Driver code int main(void) {  int arr[] = { 2, 3, 4, 10, 40 };  int n = sizeof(arr) / sizeof(arr[0]);  int x = 10;  int result = binarySearch(arr, 0, n - 1, x);  (result == -1) ? printf('Element is not present'  ' in array')  : printf('Element is present at '  'index %d',  result);  return 0; }>
Java 
// Java implementation of iterative Binary Search import java.io.*; class BinarySearch {    // Returns index of x if it is present in arr[].  int binarySearch(int arr[], int x)  {  int low = 0, high = arr.length - 1;  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was  // not present  return -1;  }  // Driver code  public static void main(String args[])  {  BinarySearch ob = new BinarySearch();  int arr[] = { 2, 3, 4, 10, 40 };  int n = arr.length;  int x = 10;  int result = ob.binarySearch(arr, x);  if (result == -1)  System.out.println(  'Element is not present in array');  else  System.out.println('Element is present at '  + 'index ' + result);  } }>
Python 
# Python3 code to implement iterative Binary # Search. # It returns location of x in given array arr def binarySearch(arr, low, high, x): while low <= high: mid = low + (high - low) // 2 # Check if x is present at mid if arr[mid] == x: return mid # If x is greater, ignore left half elif arr[mid] < x: low = mid + 1 # If x is smaller, ignore right half else: high = mid - 1 # If we reach here, then the element # was not present return -1 # Driver Code if __name__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # Function call result = binarySearch(arr, 0, len(arr)-1, x) if result != -1: print('Element is present at index', result) else: print('Element is not present in array')>
C# 
// C# implementation of iterative Binary Search using System; class GFG {    // Returns index of x if it is present in arr[]  static int binarySearch(int[] arr, int x)  {  int low = 0, high = arr.Length - 1;  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was  // not present  return -1;  }  // Driver code  public static void Main()  {  int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.Length;  int x = 10;  int result = binarySearch(arr, x);  if (result == -1)  Console.WriteLine(  'Element is not present in array');  else  Console.WriteLine('Element is present at '  + 'index ' + result);  } }>
Javascript 
// Program to implement iterative Binary Search   // A iterative binary search function. It returns // location of x in given array arr[l..r] is present, // otherwise -1  function binarySearch(arr, x) {   let low = 0;  let high = arr.length - 1;  let mid;  while (high>= niedrig) { mid = niedrig + Math.floor((hoch - niedrig) / 2);    // Wenn das Element in der Mitte // selbst vorhanden ist if (arr[mid] == x) return mid;    // Wenn das Element kleiner als mid ist, // kann es nur im linken Subarray vorhanden sein, wenn (arr[mid]> x) high = mid - 1;    // Sonst kann das Element nur // im rechten Subarray vorhanden sein sonst low = mid + 1;  } // Wir gelangen hierher, wenn das Element nicht // im Array vorhanden ist return -1; } arr =new Array(2, 3, 4, 10, 40);  x = 10;  n = arr.length;  Ergebnis = BinarySearch(arr, x);   (Ergebnis == -1) ? console.log('Element ist im Array nicht vorhanden'): console.log ('Element ist am Index vorhanden ' + Ergebnis);   // Dieser Code wurde von simranarora5sos und rshuklabbb>'> beigesteuertPHP>
Ausgabe 
Element is present at index 3>

Zeitkomplexität: O(log N)
Hilfsraum: O(1)

Rekursiver binärer Suchalgorithmus:

Erstellen Sie eine rekursive Funktion und vergleichen Sie die Mitte des Suchraums mit dem Schlüssel. Und basierend auf dem Ergebnis wird entweder der Index zurückgegeben, in dem sich der Schlüssel befindet, oder die rekursive Funktion für den nächsten Suchbereich aufgerufen.

Implementierung des rekursiven binären Suchalgorithmus:

C++ 
#include  using namespace std; // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 int binarySearch(int arr[], int low, int high, int x) {  if (high>= niedrig) { int mid = niedrig + (hoch - niedrig) / 2;  // Wenn das Element in der Mitte // selbst vorhanden ist if (arr[mid] == x) return mid;  // Wenn das Element kleiner als die Mitte ist, // kann es nur im linken Subarray vorhanden sein, wenn (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Andernfalls kann das Element nur // im rechten Subarray vorhanden sein. return binarySearch(arr, mid + 1, high, x);  } } // Treibercode int main() { int arr[] = { 2, 3, 4, 10, 40 };  int-Abfrage = 10;  int n = sizeof(arr) / sizeof(arr[0]);  int result = BinarySearch(arr, 0, n - 1, query);  (Ergebnis == -1) ? cout<< 'Element is not present in array'  : cout << 'Element is present at index ' << result;  return 0; }>
C 
// C program to implement recursive Binary Search #include  // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 int binarySearch(int arr[], int low, int high, int x) {  if (high>= niedrig) { int mid = niedrig + (hoch - niedrig) / 2;  // Wenn das Element in der Mitte // selbst vorhanden ist if (arr[mid] == x) return mid;  // Wenn das Element kleiner als die Mitte ist, // kann es nur im linken Subarray vorhanden sein, wenn (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Andernfalls kann das Element nur // im rechten Subarray vorhanden sein. return binarySearch(arr, mid + 1, high, x);  } // Wir gelangen hierher, wenn das Element nicht // im Array vorhanden ist return -1; } // Treibercode int main() { int arr[] = { 2, 3, 4, 10, 40 };  int n = sizeof(arr) / sizeof(arr[0]);  int x = 10;  int result = BinarySearch(arr, 0, n - 1, x);  (Ergebnis == -1) ? printf('Element ist im Array nicht vorhanden'): printf('Element ist am Index %d vorhanden', Ergebnis);  0 zurückgeben; }>
Java 
// Java implementation of recursive Binary Search class BinarySearch {  // Returns index of x if it is present in arr[low..  // high], else return -1  int binarySearch(int arr[], int low, int high, int x)  {  if (high>= niedrig) { int mid = niedrig + (hoch - niedrig) / 2;  // Wenn das Element in der // Mitte selbst vorhanden ist if (arr[mid] == x) return mid;  // Wenn das Element kleiner als die Mitte ist, // kann es nur im linken Subarray vorhanden sein, wenn (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Andernfalls kann das Element nur // im rechten Subarray vorhanden sein. return binarySearch(arr, mid + 1, high, x);  } // Wir gelangen hierher, wenn das Element nicht vorhanden ist // im Array return -1;  } // Treibercode public static void main(String args[]) { BinarySearch ob = new BinarySearch();  int arr[] = { 2, 3, 4, 10, 40 };  int n = arr.length;  int x = 10;  int result = ob.binarySearch(arr, 0, n - 1, x);  if (result == -1) System.out.println( 'Element ist nicht im Array vorhanden');  else System.out.println( 'Element ist am Index vorhanden ' + result);  } } /* Dieser Code wurde von Rajat Mishra beigesteuert */>
Python 
# Python3 Program for recursive binary search. # Returns index of x in arr if present, else -1 def binarySearch(arr, low, high, x): # Check base case if high>= low: mid = low + (high - low) // 2 # Wenn das Element in der Mitte selbst vorhanden ist, if arr[mid] == x: return mid # Wenn das Element kleiner als mid ist, kann es # nur vorhanden sein im linken Subarray elif arr[mid]> x: return BinarySearch(arr, low, mid-1, x) # Sonst kann das Element nur vorhanden sein # im rechten Subarray else: Return BinarySearch(arr, Mid + 1, High, x ) # Element ist im Array nicht vorhanden, sonst: return -1 # Treibercode, wenn __name__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # Funktionsaufrufergebnis = binäreSuche( arr, 0, len(arr)-1, x) if result != -1: print('Element is present at index', result) else: print('Element is not present in array')>
C# 
// C# implementation of recursive Binary Search using System; class GFG {  // Returns index of x if it is present in  // arr[low..high], else return -1  static int binarySearch(int[] arr, int low, int high, int x)  {  if (high>= niedrig) { int mid = niedrig + (hoch - niedrig) / 2;  // Wenn das Element in der // Mitte selbst vorhanden ist if (arr[mid] == x) return mid;  // Wenn das Element kleiner als die Mitte ist, // kann es nur im linken Subarray vorhanden sein, wenn (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Andernfalls kann das Element nur // im rechten Subarray vorhanden sein. return binarySearch(arr, mid + 1, high, x);  } // Wir gelangen hierher, wenn das Element nicht vorhanden ist // im Array return -1;  } // Treibercode public static void Main() { int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.Length;  int x = 10;  int result = BinarySearch(arr, 0, n - 1, x);  if (result == -1) Console.WriteLine( 'Element ist in Arrau nicht vorhanden');  else Console.WriteLine('Element ist am Index vorhanden ' + Ergebnis);  } } // Dieser Code wurde von Sam007 beigesteuert.>
Javascript 
// JavaScript program to implement recursive Binary Search // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 function binarySearch(arr, low, high, x){  if (high>= niedrig) { let mid = low + Math.floor((high - low) / 2);  // Wenn das Element in der Mitte // selbst vorhanden ist if (arr[mid] == x) return mid;  // Wenn das Element kleiner als die Mitte ist, // kann es nur im linken Subarray vorhanden sein, wenn (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Andernfalls kann das Element nur // im rechten Subarray vorhanden sein. return binarySearch(arr, mid + 1, high, x);  } // Wir gelangen hierher, wenn das Element nicht // im Array vorhanden ist return -1; } let arr = [ 2, 3, 4, 10, 40 ]; sei x = 10; let n = arr.length let result = BinarySearch(arr, 0, n - 1, x); (Ergebnis == -1) ? console.log( 'Element ist im Array nicht vorhanden'): console.log('Element ist am Index vorhanden ' +result);>
PHP 
 // PHP program to implement // recursive Binary Search // A recursive binary search // function. It returns location // of x in given array arr[low..high]  // is present, otherwise -1 function binarySearch($arr, $low, $high, $x) { if ($high>= $low) { $mid = ceil($low + ($high - $low) / 2); // Wenn das Element vorhanden ist // in der Mitte selbst if ($arr[$mid] == $x) return floor($mid); // Wenn das Element kleiner als // mid ist, kann es // nur dann im linken Subarray vorhanden sein, wenn ($arr[$mid]> $x) binäreSuche($arr, $low, $mid - 1, $x) zurückgibt ); // Andernfalls kann das Element nur // im rechten Subarray vorhanden sein. return binarySearch($arr, $mid + 1, $high, $x); } // Wir gelangen hierher, wenn das Element // nicht im Array vorhanden ist return -1; } // Treibercode $arr = array(2, 3, 4, 10, 40); $n = count($arr); $x = 10; $result = BinarySearch($arr, 0, $n - 1, $x); if(($result == -1)) echo 'Element ist im Array nicht vorhanden'; else echo 'Element ist am Index vorhanden ', $result; ?>>
Ausgabe 
Element is present at index 3>
  • Zeitkomplexität:
    • Bester Fall: O(1)
    • Durchschnittlicher Fall: O(log N)
    • Schlimmster Fall: O(log N)
  • Hilfsraum: O(1). Wenn der rekursive Aufrufstapel berücksichtigt wird, ist der Hilfsraum O(logN).
  • Die binäre Suche kann als Baustein für komplexere Algorithmen verwendet werden, die beim maschinellen Lernen verwendet werden, beispielsweise Algorithmen zum Training neuronaler Netze oder zum Finden der optimalen Hyperparameter für ein Modell.
  • Es kann für die Suche in Computergrafiken wie Algorithmen für Raytracing oder Texture Mapping verwendet werden.
  • Es kann zum Durchsuchen einer Datenbank verwendet werden.
  • Die binäre Suche ist schneller als die lineare Suche, insbesondere bei großen Arrays.
  • Effizienter als andere Suchalgorithmen mit ähnlicher zeitlicher Komplexität, wie z. B. die Interpolationssuche oder die exponentielle Suche.
  • Die binäre Suche eignet sich gut zum Durchsuchen großer Datensätze, die in einem externen Speicher, beispielsweise auf einer Festplatte oder in der Cloud, gespeichert sind.
  • Das Array sollte sortiert sein.
  • Bei der binären Suche muss die durchsuchte Datenstruktur an zusammenhängenden Speicherorten gespeichert werden.
  • Bei der binären Suche müssen die Elemente des Arrays vergleichbar sein, d. h. sie müssen geordnet werden können.

Häufig gestellte Fragen (FAQs) zur binären Suche:

1. Was ist binäre Suche?

Die binäre Suche ist ein effizienter Algorithmus zum Finden eines Zielwerts innerhalb eines sortierten Arrays. Es funktioniert durch wiederholtes Teilen des Suchintervalls in zwei Hälften.

2. Wie funktioniert die binäre Suche?

Die binäre Suche vergleicht den Zielwert mit dem mittleren Element des Arrays. Sind sie gleich, ist die Suche erfolgreich. Wenn das Ziel kleiner als das mittlere Element ist, wird die Suche in der unteren Hälfte des Arrays fortgesetzt. Ist das Ziel größer, wird die Suche in der oberen Hälfte fortgesetzt. Dieser Vorgang wiederholt sich, bis das Ziel gefunden wird oder das Suchintervall leer ist.

3. Wie hoch ist die zeitliche Komplexität der binären Suche?

Die zeitliche Komplexität der binären Suche beträgt O(log2n), wobei n die Anzahl der Elemente im Array ist. Dies liegt daran, dass sich die Größe des Suchintervalls in jedem Schritt halbiert.

Ameise gegen Maven

4. Was sind die Voraussetzungen für die binäre Suche?

Die binäre Suche erfordert, dass das Array in aufsteigender oder absteigender Reihenfolge sortiert wird. Wenn das Array nicht sortiert ist, können wir die binäre Suche nicht zum Durchsuchen eines Elements im Array verwenden.

5. Was passiert, wenn das Array für die binäre Suche nicht sortiert ist?

Wenn das Array nicht sortiert ist, kann die binäre Suche falsche Ergebnisse liefern. Es basiert auf der Sortierung des Arrays, um Entscheidungen darüber zu treffen, welche Hälfte des Arrays durchsucht werden soll.

6. Kann die binäre Suche auf nicht numerische Daten angewendet werden?

Ja, die binäre Suche kann auf nicht numerische Daten angewendet werden, solange eine definierte Reihenfolge für die Elemente vorliegt. Beispielsweise können damit Zeichenfolgen in alphabetischer Reihenfolge gesucht werden.

7. Was sind einige häufige Nachteile der binären Suche?

Der Nachteil der binären Suche besteht darin, dass das Eingabearray sortiert werden muss, um zu entscheiden, welches in welcher Hälfte das Zielelement liegen kann. Daher müssen wir bei unsortierten Arrays das Array sortieren, bevor wir die binäre Suche anwenden.

8. Wann sollte die binäre Suche verwendet werden?

Bei der Suche nach einem Zielwert in einem sortierten Array sollte die binäre Suche verwendet werden, insbesondere wenn das Array groß ist. Es ist im Vergleich zu linearen Suchalgorithmen besonders effizient für große Datensätze.

9. Kann die binäre Suche rekursiv implementiert werden?

Ja, die binäre Suche kann sowohl iterativ als auch rekursiv implementiert werden. Die rekursive Implementierung führt häufig zu prägnanterem Code, kann jedoch aufgrund von rekursivem Stapelspeicherplatz oder Funktionsaufrufen einen etwas höheren Overhead verursachen.

10. Ist die binäre Suche immer die beste Wahl für die Suche in einem sortierten Array?

Während die binäre Suche für die Suche in sortierten Arrays sehr effizient ist, kann es bestimmte Fälle geben, in denen andere Suchalgorithmen besser geeignet sind, beispielsweise beim Umgang mit kleinen Datensätzen oder wenn das Array häufig geändert wird.

In Verbindung stehende Artikel:

  • Binäre Suche im Antwort-Tutorial mit Problemen
  • Lineare Suche vs. binäre Suche
  • Wie kann man Probleme bei der binären Suche identifizieren und lösen?