Binäre Suche ist eine Suchtechnik, die auf der funktioniert Divide-and-Conquer-Ansatz . Es wird verwendet, um nach einem beliebigen Element in einem sortierten Array zu suchen. Im Vergleich zur linearen Suche ist die binäre Suche mit einer Zeitkomplexität von O(logN) viel schneller, während die lineare Suche mit einer Zeitkomplexität von O(N) funktioniert
Beispiele :
Input : arr[] = {1, 3, 5, 7, 8, 9}, x = 5 Output : Element found! Input : arr[] = {1, 3, 5, 7, 8, 9}, x = 6 Output : Element not found!> Notiz: Vorausgesetzt, das Array ist sortiert.
Dies sind die folgenden Möglichkeiten, die binäre Suche in JavaScript durchzuführen:
Inhaltsverzeichnis
Rekursiver Ansatz:
- GRUNDZUSTAND: Wenn der Startindex größer als der Endindex ist, wird „false“ zurückgegeben.
- Berechnen Sie den mittleren Index.
- Vergleichen Sie das mittlere Element mit der Zahl x. Bei Gleichheit wird „true“ zurückgegeben.
- Wenn größer, rufen Sie dieselbe Funktion mit dem Endindex = middle-1 auf und wiederholen Sie Schritt 1.
- Wenn kleiner, rufen Sie dieselbe Funktion mit Startindex = Mitte+1 auf und wiederholen Sie Schritt 1.
Beispiel: Dieses Beispiel zeigt die Verwendung des oben erläuterten Ansatzes.
Javascript
Excel-Datei in Java lesen
let recursiveFunction =>function> (arr, x, start, end) {> >// Base Condition> >if> (start>Ende)>return> false>;> >// Find the middle index> >let mid = Math.floor((start + end) / 2);> >// Compare mid with given key x> >if> (arr[mid] === x)>return> true>;> >// If element at mid is greater than x,> >// search in the left half of mid> >if> (arr[mid]>x)> >return> recursiveFunction(arr, x, start, mid - 1);> >else> >// If element at mid is smaller than x,> >// search in the right half of mid> >return> recursiveFunction(arr, x, mid + 1, end);> }> // Driver code> let arr = [1, 3, 5, 7, 8, 9];> let x = 5;> if> (recursiveFunction(arr, x, 0, arr.length - 1)) {> >console.log(>'Element found!'>);> }> else> { console.log(>'Element not found!'>); }> x = 6;> if> (recursiveFunction(arr, x, 0, arr.length - 1)) {> >console.log(>'Element found!'>);> }> else> { console.log(>'Element not found!'>); }> |
>
>Ausgabe
Element found! Element not found!>
Zeitkomplexität: O(logN)
Hilfsraum: O(1)
Iterativer Ansatz:
Bei diesem iterativen Ansatz verwenden wir anstelle einer Rekursion eine while-Schleife, und die Schleife läuft, bis sie die Grundbedingung erreicht, d. h. der Start wird größer als das Ende.
Beispiel: Dieses Beispiel zeigt die Verwendung des oben erläuterten Ansatzes.
Javascript
Beispiel einer Java-Klasse
// Iterative function to implement Binary Search> let iterativeFunction =>function> (arr, x) {> >let start = 0, end = arr.length - 1;> >// Iterate while start not meets end> >while> (start <= end) {> >// Find the mid index> >let mid = Math.floor((start + end) / 2);> >// If element is present at> >// mid, return True> >if> (arr[mid] === x)>return> true>;> >// Else look in left or> >// right half accordingly> >else> if> (arr[mid] start = mid + 1; else end = mid - 1; } return false; } // Driver code let arr = [1, 3, 5, 7, 8, 9]; let x = 5; if (iterativeFunction(arr, x, 0, arr.length - 1)) { console.log('Element found!'); } else { console.log('Element not found!'); } x = 8; if (iterativeFunction(arr, x, 0, arr.length - 1)) { console.log('Element found!'); } else { console.log('Element not found!'); }> |
>
>Ausgabe
Element found! Element found!>
Zeitkomplexität: O(logN).
Hilfsraum: O(1)