Binaire zoekopdracht is een zoektechniek die werkt op de Verdeel en heers-aanpak . Het wordt gebruikt om naar elk element in een gesorteerde array te zoeken. Vergeleken met lineair is binair zoeken veel sneller met een tijdscomplexiteit van O(logN), terwijl lineair zoeken werkt in O(N) tijdscomplexiteit
apurva padgaonkar
Voorbeelden :
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!> Opmerking: Ervan uitgaande dat de array is gesorteerd.
Dit zijn de volgende manieren om binair zoeken in JavaScript uit te voeren:
Inhoudsopgave
Recursieve aanpak:
- BASISCONDITIE: Als de startindex groter is dan de eindindex, retourneert false.
- Bereken de middelste index.
- Vergelijk het middelste element met het getal x. Als gelijk resultaat waar is.
- Indien groter, roep dan dezelfde functie aan met eindindex = midden-1 en herhaal stap 1.
- Indien kleiner, roep dan dezelfde functie aan met startindex = midden+1 en herhaal stap 1.
Voorbeeld: Dit voorbeeld toont het gebruik van de hierboven uitgelegde aanpak.
javascript
let recursiveFunction =>function> (arr, x, start, end) {> >// Base Condition> >if> (start>einde)>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!'>); }> |
selecteer sql uit meerdere tabellen
>
>Uitvoer
Element found! Element not found!>
Tijdcomplexiteit: O(logN)
Hulpruimte: O(1)
Iteratieve aanpak:
In deze iteratieve benadering gebruiken we in plaats van recursie een while-lus, en de lus loopt totdat deze de basisvoorwaarde bereikt, d.w.z. dat het begin groter wordt dan het einde.
Voorbeeld: Dit voorbeeld toont het gebruik van de hierboven uitgelegde aanpak.
javascript
poort luisteren
// 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!'); }> |
>
>Uitvoer
Element found! Element found!>
Tijdcomplexiteit: O(logN).
Hulpruimte: O(1)