logo

TechCodeview

Binair zoekalgoritme – iteratieve en recursieve implementatie

Binaire zoekopdracht Algoritme is een zoekalgoritme gebruikt in een gesorteerde array op herhaaldelijk het zoekinterval in tweeën delen . Het idee van binair zoeken is om de informatie te gebruiken dat de array is gesorteerd en de tijdscomplexiteit te reduceren tot O(log N).

Binaire zoekopdracht is een zoekalgoritme dat wordt gebruikt om de positie van een doelwaarde binnen a te vinden gesorteerd reeks. Het werkt door het zoekinterval herhaaldelijk in tweeën te delen totdat de doelwaarde is gevonden of het interval leeg is. Het zoekinterval wordt gehalveerd door het doelelement te vergelijken met de middelste waarde van de zoekruimte.

gelijk aan Java

Om het binaire zoekalgoritme toe te passen:



  • De datastructuur moet worden gesorteerd.
  • Toegang tot elk element van de datastructuur kost constante tijd.

Binair zoekalgoritme:

In dit algoritme

  • Verdeel de zoekruimte in twee helften door het vinden van de middelste index midden .

Het vinden van de middelste index midden in het binaire zoekalgoritme

  • Vergelijk het middelste element van de zoekruimte met de sleutel.
  • Als de sleutel op het middelste element wordt gevonden, wordt het proces beëindigd.
  • Als de sleutel niet wordt gevonden in het middelste element, kies dan welke helft wordt gebruikt als de volgende zoekruimte.
    • Als de sleutel kleiner is dan het middelste element, wordt de linkerkant gebruikt voor de volgende zoekopdracht.
    • Als de sleutel groter is dan het middelste element, wordt de rechterkant gebruikt voor de volgende zoekopdracht.
  • Dit proces wordt voortgezet totdat de sleutel is gevonden of de totale zoekruimte is uitgeput.

Hoe werkt het binaire zoekalgoritme?

Bekijk de volgende illustratie om de werking van binair zoeken te begrijpen:

Overweeg een array arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} , en de doel = 23 .

Eerste stap: Bereken het midden en vergelijk het middenelement met de sleutel. Als de sleutel kleiner is dan het middenelement, ga dan naar links en als deze groter is dan het midden, verplaats dan de zoekruimte naar rechts.

  • Sleutel (d.w.z. 23) is groter dan het huidige middenelement (d.w.z. 16). De zoekruimte beweegt naar rechts.

Binair zoekalgoritme: vergelijk sleutel met 16

  • Sleutel is kleiner dan de huidige midden 56. De zoekruimte beweegt naar links.

Binair zoekalgoritme: vergelijk sleutel met 56

Tweede stap: Als de sleutel overeenkomt met de waarde van het middelste element, wordt het element gevonden en wordt het zoeken gestopt.

Binair zoekalgoritme: sleutelovereenkomsten met midden

Aanbevolen praktijk Binair zoeken Probeer het!

De Binair zoekalgoritme kan op de volgende twee manieren worden geïmplementeerd

  • Iteratief binair zoekalgoritme
  • Recursief binair zoekalgoritme

Hieronder vindt u de pseudocodes voor de benaderingen.

Iteratief binair zoekalgoritme:

Hier gebruiken we een while-lus om het proces van het vergelijken van de sleutel voort te zetten en de zoekruimte in twee helften te splitsen.

Implementatie van iteratief binair zoekalgoritme:

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>= laag) { midden = laag + Math.floor((hoog - laag) / 2);    // Als het element in het midden aanwezig is // zichzelf als (arr[mid] == x) midden terugkeert;    // Als het element kleiner is dan mid, dan // kan het alleen aanwezig zijn in de linker subarray als (arr[mid]> x) high = mid - 1;    // Anders kan het element alleen aanwezig zijn // in de rechter subarray else low = mid + 1;  } // We komen hier wanneer het element niet // aanwezig is in array return -1; } arr =nieuwe Array(2, 3, 4, 10, 40);  x = 10;  n = arr.lengte;  resultaat = binair zoeken(arr, x);   (resultaat == -1) ? console.log('Element is niet aanwezig in array') : console.log ('Element is aanwezig in index' + resultaat);   // Deze code is bijgedragen door simranarora5sos en rshuklabbb>
PHP 
 // PHP program to implement // iterative Binary Search // An iterative binary search  // function function 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 floor($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 $arr = array(2, 3, 4, 10, 40); $n = count($arr); $x = 10; $result = binarySearch($arr, 0, $n - 1, $x); if(($result == -1)) echo 'Element is not present in array'; else echo 'Element is present at index ', $result; // This code is contributed by anuj_67. ?>>
Uitvoer 
Element is present at index 3>

Tijdcomplexiteit: O(log N)
Hulpruimte: O(1)

Recursief binair zoekalgoritme:

Maak een recursieve functie en vergelijk het midden van de zoekruimte met de sleutel. En op basis van het resultaat retourneer je de index waar de sleutel is gevonden, of roep je de recursieve functie aan voor de volgende zoekruimte.

Implementatie van recursief binair zoekalgoritme:

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>= laag) { int midden = laag + (hoog - laag) / 2;  // Als het element in het midden aanwezig is // zichzelf als (arr[mid] == x) midden terugkeert;  // Als het element kleiner is dan mid, // kan het alleen aanwezig zijn in de linker subarray als (arr[mid]> x) binarySearch(arr, low, mid - 1, x) retourneert;  // Anders kan het element alleen aanwezig zijn // in de rechter subarray return binarySearch(arr, mid + 1, high, x);  } } // Stuurprogrammacode int main() { int arr[] = { 2, 3, 4, 10, 40 };  int-query = 10;  int n = groottevan(arr) / groottevan(arr[0]);  int resultaat = binarySearch(arr, 0, n - 1, zoekopdracht);  (resultaat == -1) ? uit<< '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>= laag) { int midden = laag + (hoog - laag) / 2;  // Als het element in het midden aanwezig is // zichzelf als (arr[mid] == x) midden terugkeert;  // Als het element kleiner is dan mid, // kan het alleen aanwezig zijn in de linker subarray als (arr[mid]> x) binarySearch(arr, low, mid - 1, x) retourneert;  // Anders kan het element alleen aanwezig zijn // in de rechter subarray return binarySearch(arr, mid + 1, high, x);  } // We komen hier wanneer het element niet // aanwezig is in array return -1; } // Stuurprogrammacode int main() { int arr[] = { 2, 3, 4, 10, 40 };  int n = groottevan(arr) / groottevan(arr[0]);  intx = 10;  int resultaat = binarySearch(arr, 0, n - 1, x);  (resultaat == -1) ? printf('Element is niet aanwezig in array') : printf('Element is aanwezig in index %d', resultaat);  retour 0; }>
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>= laag) { int midden = laag + (hoog - laag) / 2;  // Als het element aanwezig is in het // midden zelf als (arr[mid] == x) halverwege terugkeert;  // Als het element kleiner is dan mid, // kan het alleen aanwezig zijn in de linker subarray als (arr[mid]> x) binarySearch(arr, low, mid - 1, x) retourneert;  // Anders kan het element alleen aanwezig zijn // in de rechter subarray return binarySearch(arr, mid + 1, high, x);  } // We komen hier wanneer het element niet aanwezig is // in array return -1;  } // Stuurprogrammacode public static void main(String args[]) { BinarySearch ob = new BinarySearch();  int arr[] = { 2, 3, 4, 10, 40 };  int n = arr.lengte;  intx = 10;  int resultaat = ob.binarySearch(arr, 0, n - 1, x);  if (resultaat == -1) System.out.println( 'Element is niet aanwezig in array');  else System.out.println( 'Element is aanwezig in index ' + resultaat);  } } /* Deze code is bijgedragen door Rajat Mishra */>
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>= laag: midden = laag + (hoog - laag) // 2 # Als element aanwezig is in het midden zelf if arr[mid] == x: return mid # Als element kleiner is dan mid, dan kan het # alleen aanwezig zijn in linker subarray elif arr[mid]> x: return binarySearch(arr, low, mid-1, x) # Anders kan het element alleen aanwezig zijn # in rechter subarray else: return binarySearch(arr, mid + 1, high, x ) # Element is niet aanwezig in de array anders: return -1 # Stuurprogrammacode if __name__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # Functieaanroepresultaat = binarySearch( arr, 0, len(arr)-1, x) if resultaat != -1: print('Element is aanwezig in index', resultaat) else: print('Element is niet aanwezig 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>= laag) { int midden = laag + (hoog - laag) / 2;  // Als het element aanwezig is in het // midden zelf als (arr[mid] == x) halverwege terugkeert;  // Als het element kleiner is dan mid, // kan het alleen aanwezig zijn in de linker subarray als (arr[mid]> x) binarySearch(arr, low, mid - 1, x) retourneert;  // Anders kan het element alleen aanwezig zijn // in de rechter subarray return binarySearch(arr, mid + 1, high, x);  } // We komen hier wanneer het element niet aanwezig is // in array return -1;  } // Stuurprogrammacode public static void Main() { int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.Lengte;  intx = 10;  int resultaat = binarySearch(arr, 0, n - 1, x);  if (resultaat == -1) Console.WriteLine( 'Element is niet aanwezig in arrau');  else Console.WriteLine('Element is aanwezig in index ' + resultaat);  } } // Deze code is bijgedragen door Sam007.>
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>= laag) { laat midden = laag + Math.floor((hoog - laag) / 2);  // Als het element in het midden aanwezig is // zichzelf als (arr[mid] == x) midden terugkeert;  // Als het element kleiner is dan mid, dan // kan het alleen aanwezig zijn in de linker subarray als (arr[mid]> x) binarySearch(arr, low, mid - 1, x) retourneert;  // Anders kan het element alleen aanwezig zijn // in de rechter subarray return binarySearch(arr, mid + 1, high, x);  } // We komen hier wanneer het element niet // aanwezig is in array return -1; } laat arr = [ 2, 3, 4, 10, 40 ]; laat x = 10; laat n = arr.lengte laat resultaat = binarySearch(arr, 0, n - 1, x); (resultaat == -1) ? console.log('Element is niet aanwezig in array'): console.log('Element is aanwezig in index' +resultaat);>
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>= $laag) { $mid = plafond($laag + ($hoog - $laag) / 2); // Als het element aanwezig is // in het midden zelf if ($arr[$mid] == $x) return floor($mid); // Als het element kleiner is dan // mid, dan kan het alleen // aanwezig zijn in de linker subarray als ($arr[$mid]> $x) binarySearch($arr, $low, $mid - 1, $x) retourneert ); // Anders kan het element alleen // aanwezig zijn in de rechter subarray return binarySearch($arr, $mid + 1, $high, $x); } // We komen hier wanneer element // niet aanwezig is in array return -1; } // Stuurprogrammacode $arr = array(2, 3, 4, 10, 40); $n = aantal($arr); $x = 10; $result = binarySearch($arr, 0, $n - 1, $x); if(($result == -1)) echo 'Element is niet aanwezig in array'; else echo 'Element is aanwezig in index ', $result; ?>>
Uitvoer 
Element is present at index 3>
  • Tijdcomplexiteit:
    • Beste geval: O(1)
    • Gemiddeld geval: O(log N)
    • Slechtste geval: O(log N)
  • Hulpruimte: O(1), als de recursieve call-stack in aanmerking wordt genomen, zal de hulpruimte O(logN) zijn.
  • Binair zoeken kan worden gebruikt als bouwsteen voor complexere algoritmen die worden gebruikt bij machinaal leren, zoals algoritmen voor het trainen van neurale netwerken of het vinden van de optimale hyperparameters voor een model.
  • Het kan worden gebruikt voor het zoeken in computergraphics, zoals algoritmen voor ray tracing of texture mapping.
  • Het kan worden gebruikt voor het doorzoeken van een database.
  • Binair zoeken is sneller dan lineair zoeken, vooral voor grote arrays.
  • Efficiënter dan andere zoekalgoritmen met een vergelijkbare tijdscomplexiteit, zoals zoeken via interpolatie of exponentieel zoeken.
  • Binair zoeken is zeer geschikt voor het doorzoeken van grote datasets die zijn opgeslagen in een extern geheugen, zoals op een harde schijf of in de cloud.
  • De array moet worden gesorteerd.
  • Binair zoeken vereist dat de datastructuur die wordt doorzocht, wordt opgeslagen in aaneengesloten geheugenlocaties.
  • Binair zoeken vereist dat de elementen van de array vergelijkbaar zijn, wat betekent dat ze geordend moeten kunnen worden.

Veelgestelde vragen (FAQ's) over binair zoeken:

1. Wat is binair zoeken?

Binair zoeken is een efficiënt algoritme voor het vinden van een doelwaarde binnen een gesorteerde array. Het werkt door het zoekinterval herhaaldelijk in tweeën te delen.

2. Hoe werkt binair zoeken?

Binary Search vergelijkt de doelwaarde met het middelste element van de array. Als ze gelijk zijn, is de zoekopdracht succesvol. Als het doel kleiner is dan het middelste element, wordt het zoeken voortgezet in de onderste helft van de array. Als het doelwit groter is, gaat de zoektocht verder in de bovenste helft. Dit proces herhaalt zich totdat het doel is gevonden of het zoekinterval leeg is.

3. Wat is de tijdscomplexiteit van binair zoeken?

De tijdscomplexiteit van binair zoeken is O(log2n), waarbij n het aantal elementen in de array is. Dit komt omdat de grootte van het zoekinterval bij elke stap wordt gehalveerd.

4. Wat zijn de vereisten voor binair zoeken?

Binair zoeken vereist dat de array in oplopende of aflopende volgorde wordt gesorteerd. Als de array niet is gesorteerd, kunnen we Binary Search niet gebruiken om een ​​element in de array te doorzoeken.

5. Wat gebeurt er als de array niet is gesorteerd voor binair zoeken?

Als de array niet is gesorteerd, kan binair zoeken onjuiste resultaten opleveren. Het is afhankelijk van de gesorteerde aard van de array om beslissingen te nemen over welke helft van de array moet worden doorzocht.

6. Kan binair zoeken worden toegepast op niet-numerieke gegevens?

Ja, binair zoeken kan worden toegepast op niet-numerieke gegevens, zolang er een gedefinieerde volgorde voor de elementen is. Het kan bijvoorbeeld worden gebruikt om tekenreeksen in alfabetische volgorde te zoeken.

7. Wat zijn enkele veelvoorkomende nadelen van binair zoeken?

Het nadeel van Binary Search is dat de invoerarray moet worden gesorteerd om te beslissen in welke helft het doelelement kan liggen. Daarom moeten we voor ongesorteerde arrays de array sorteren voordat we Binary Search toepassen.

8. Wanneer moet binair zoeken worden gebruikt?

Binair zoeken moet worden gebruikt bij het zoeken naar een doelwaarde in een gesorteerde array, vooral als de omvang van de array groot is. Het is bijzonder efficiënt voor grote datasets in vergelijking met lineaire zoekalgoritmen.

9. Kan binair zoeken recursief worden geïmplementeerd?

Ja, binair zoeken kan zowel iteratief als recursief worden geïmplementeerd. De recursieve implementatie leidt vaak tot beknoptere code, maar kan iets hogere overhead met zich meebrengen vanwege recursieve stapelruimte of functieaanroepen.

java int als tekenreeks

10. Is binair zoeken altijd de beste keuze voor het zoeken in een gesorteerde array?

Hoewel binair zoeken zeer efficiënt is bij het zoeken in gesorteerde arrays, kunnen er specifieke gevallen zijn waarin andere zoekalgoritmen geschikter zijn, bijvoorbeeld bij het omgaan met kleine datasets of wanneer de array regelmatig wordt gewijzigd.

Gerelateerde artikelen:

  • Binair zoeken op antwoordhandleiding met problemen
  • Lineair zoeken versus binair zoeken
  • Hoe binaire zoekproblemen te identificeren en op te lossen?