logo

TechCodeview

Binær søkealgoritme – Iterativ og rekursiv implementering

Binært søk Algoritme er en søkealgoritme brukes i en sortert matrise etter gjentatte ganger deler søkeintervallet i to . Ideen med binært søk er å bruke informasjonen om at matrisen er sortert og redusere tidskompleksiteten til O(log N).

Binært søk er en søkealgoritme som brukes til å finne posisjonen til en målverdi innenfor en sortert array. Det fungerer ved å gjentatte ganger dele søkeintervallet i to til målverdien er funnet eller intervallet er tomt. Søkeintervallet halveres ved å sammenligne målelementet med den midterste verdien av søkerommet.

union vs union alle

Slik bruker du binær søkealgoritme:



  • Datastrukturen må sorteres.
  • Tilgang til ethvert element i datastrukturen tar konstant tid.

Binær søkealgoritme:

I denne algoritmen,

  • Del søkefeltet i to halvdeler ved å finne midtindeksen midt .

Finne midtindeksen midt i binær søkealgoritme

  • Sammenlign det midterste elementet i søkefeltet med nøkkelen.
  • Hvis nøkkelen finnes ved midtelementet, avsluttes prosessen.
  • Hvis nøkkelen ikke finnes ved midtelementet, velg hvilken halvdel som skal brukes som neste søkefelt.
    • Hvis nøkkelen er mindre enn midtelementet, brukes venstre side for neste søk.
    • Hvis nøkkelen er større enn midtelementet, brukes høyre side for neste søk.
  • Denne prosessen fortsetter til nøkkelen er funnet eller den totale søkeplassen er oppbrukt.

Hvordan fungerer binær søkealgoritme?

For å forstå hvordan binært søk fungerer, bør du vurdere følgende illustrasjon:

Vurder en matrise arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} , og mål = 23 .

Første skritt: Beregn midten og sammenlign midtelementet med nøkkelen. Hvis nøkkelen er mindre enn midtelementet, flytt til venstre og hvis den er større enn midten, flytt søkefeltet til høyre.

  • Nøkkel (dvs. 23) er større enn gjeldende midtelement (dvs. 16). Søkefeltet flyttes til høyre.

Binær søkealgoritme: Sammenlign nøkkel med 16

  • Nøkkelen er mindre enn den nåværende midten av 56. Søkefeltet flyttes til venstre.

Binær søkealgoritme: Sammenlign nøkkel med 56

Andre trinn: Hvis nøkkelen samsvarer med verdien til midtelementet, blir elementet funnet og stopp søket.

Binær søkealgoritme : Nøkkeltreff med mid

Anbefalt praksis binært søk Prøv det!

De Binær søkealgoritme kan implementeres på følgende to måter

  • Iterativ binær søkealgoritme
  • Rekursiv binær søkealgoritme

Nedenfor er pseudokodene for tilnærmingene.

Iterativ binær søkealgoritme:

Her bruker vi en while-løkke for å fortsette prosessen med å sammenligne nøkkelen og dele søkerommet i to halvdeler.

Implementering av iterativ binær søkealgoritme:

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>= lav) { mid = lav + Math.floor((høy - lav) / 2);    // Hvis elementet er tilstede i midten // seg selv if (arr[midt] == ​​x) returner midt;    // Hvis element er mindre enn mid, så // kan det bare være tilstede i venstre undergruppe hvis (arr[mid]> x) high = mid - 1;    // Ellers kan elementet bare være tilstede // i høyre undergruppe ellers lav = mid + 1;  } // Vi når hit når element ikke er // tilstede i array return -1; } arr =ny matrise(2, 3, 4, 10, 40);  x = 10;  n = arr.lengde;  resultat = binært søk(arr, x);   (resultat == -1) ? console.log('Element er ikke til stede i array') : console.log ('Element er til stede i indeks ' + resultat);   // Denne koden er bidratt av simranarora5sos og 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. ?>>
Produksjon 
Element is present at index 3>

Tidskompleksitet: O(log N)
Hjelpeplass: O(1)

Rekursiv binær søkealgoritme:

Lag en rekursiv funksjon og sammenlign midten av søkefeltet med tasten. Og basert på resultatet enten returner indeksen der nøkkelen er funnet eller kall den rekursive funksjonen for neste søkerom.

Implementering av rekursiv binær søkealgoritme:

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>= lav) { int mid = lav + (høy - lav) / 2;  // Hvis elementet er tilstede i midten // seg selv if (arr[midt] == ​​x) returner midt;  // Hvis elementet er mindre enn mid, så // kan det bare være tilstede i venstre subarray if (arr[midt]> x) returner binarySearch(arr, low, mid - 1, x);  // Ellers kan elementet bare være tilstede // i høyre subarray returner binarySearch(arr, mid + 1, high, x);  } } // Driverkode int main() { int arr[] = { 2, 3, 4, 10, 40 };  int query = 10;  int n = størrelse på(arr) / størrelse på(arr[0]);  int resultat = binært søk(arr, 0, n - 1, spørring);  (resultat == -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>= lav) { int mid = lav + (høy - lav) / 2;  // Hvis elementet er tilstede i midten // seg selv if (arr[midt] == ​​x) returner midt;  // Hvis elementet er mindre enn mid, så // kan det bare være tilstede i venstre subarray if (arr[midt]> x) returner binarySearch(arr, low, mid - 1, x);  // Ellers kan elementet bare være tilstede // i høyre subarray returner binarySearch(arr, mid + 1, high, x);  } // Vi når hit når element ikke er // tilstede i array return -1; } // Driverkode int main() { int arr[] = { 2, 3, 4, 10, 40 };  int n = størrelse på(arr) / størrelse på(arr[0]);  int x = 10;  int resultat = binært søk(arr, 0, n - 1, x);  (resultat == -1) ? printf('Element er ikke til stede i array') : printf('Element er til stede ved indeks %d', resultat);  returner 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>= lav) { int mid = lav + (høy - lav) / 2;  // Hvis elementet er tilstede ved // midten selv if (arr[midt] == ​​x) returner mid;  // Hvis elementet er mindre enn mid, så // kan det bare være tilstede i venstre subarray if (arr[midt]> x) returner binarySearch(arr, low, mid - 1, x);  // Ellers kan elementet bare være tilstede // i høyre subarray returner binarySearch(arr, mid + 1, high, x);  } // Vi når hit når element ikke er tilstede // i array returnerer -1;  } // Driverkode offentlig statisk void main(String args[]) { BinarySearch ob = new BinarySearch();  int arr[] = { 2, 3, 4, 10, 40 };  int n = arr.lengde;  int x = 10;  int resultat = ob.binarySearch(arr, 0, n - 1, x);  if (resultat == -1) System.out.println( 'Element er ikke til stede i array');  else System.out.println( 'Element er til stede ved indeks ' + resultat);  } } /* Denne koden er bidratt av 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>= lav: mid = lav + (høy - lav) // 2 # Hvis element er tilstede i midten selv hvis arr[mid] == x: return mid # Hvis element er mindre enn mid, så kan # bare være til stede i venstre undergruppe elif arr[midt]> x: return binært søk(arr, lav, midt-1, x) # Ellers kan elementet bare være til stede # i høyre undergruppe annet: returner binært søk(arr, mid + 1, høy, x ) # Element er ikke til stede i matrisen annet: returner -1 # Driverkode hvis __navn__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # Resultat av funksjonsanrop = binært søk( arr, 0, len(arr)-1, x) if result != -1: print('Element er til stede i indeks', resultat) else: print('Element er ikke til stede i 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>= lav) { int mid = lav + (høy - lav) / 2;  // Hvis elementet er tilstede ved // midten selv if (arr[midt] == ​​x) returner mid;  // Hvis elementet er mindre enn mid, så // kan det bare være tilstede i venstre subarray if (arr[midt]> x) returner binarySearch(arr, low, mid - 1, x);  // Ellers kan elementet bare være tilstede // i høyre subarray returner binarySearch(arr, mid + 1, high, x);  } // Vi når hit når element ikke er tilstede // i array returnerer -1;  } // Driverkode offentlig statisk void Main() { int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.Length;  int x = 10;  int resultat = binært søk(arr, 0, n - 1, x);  if (resultat == -1) Console.WriteLine( 'Element er ikke til stede i arrau');  else Console.WriteLine('Element er til stede ved indeks ' + resultat);  } } // Denne koden er bidratt av 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>= lav) { la mid = lav + Math.floor((høy - lav) / 2);  // Hvis elementet er tilstede i midten // seg selv if (arr[midt] == ​​x) returner midt;  // Hvis elementet er mindre enn mid, så // kan det bare være tilstede i venstre subarray if (arr[midt]> x) returner binarySearch(arr, low, mid - 1, x);  // Ellers kan elementet bare være tilstede // i høyre subarray returner binarySearch(arr, mid + 1, high, x);  } // Vi når hit når element ikke er // tilstede i array return -1; } la arr = [ 2, 3, 4, 10, 40 ]; la x = 10; la n = arr.length la resultat = binært søk(arr, 0, n - 1, x); (resultat == -1) ? console.log( 'Element er ikke til stede i array') : console.log('Element er til stede i indeks ' +resultat);>
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); // Hvis elementet er tilstede // i selve midten if ($arr[$mid] == $x) return floor($midt); // Hvis element er mindre enn // mid, kan det bare være // til stede i venstre undergruppe hvis ($arr[$mid]> $x) returnerer binarySearch($arr, $low, $mid - 1, $x ); // Ellers kan elementet bare // være tilstede i høyre subarray return binarySearch($arr, $mid + 1, $high, $x); } // Vi når hit når element // ikke er tilstede i array return -1; } // Driverkode $arr = array(2, 3, 4, 10, 40); $n = count($arr); $x = 10; $resultat = binært søk($arr, 0, $n - 1, $x); if(($result == -1)) ekko 'Element er ikke til stede i array'; else echo 'Element er til stede ved indeks ', $result; ?>>
Produksjon 
Element is present at index 3>
  • Tidskompleksitet:
    • Beste tilfelle: O(1)
    • Gjennomsnittlig sak: O(log N)
    • Verste tilfelle: O(log N)
  • Hjelpeplass: O(1), Hvis den rekursive anropsstakken vurderes, vil hjelperommet være O(logN).
  • Binært søk kan brukes som en byggestein for mer komplekse algoritmer som brukes i maskinlæring, for eksempel algoritmer for å trene nevrale nettverk eller finne de optimale hyperparametrene for en modell.
  • Den kan brukes til å søke i datagrafikk som algoritmer for strålesporing eller teksturkartlegging.
  • Den kan brukes til å søke i en database.
  • Binært søk er raskere enn lineært søk, spesielt for store matriser.
  • Mer effektive enn andre søkealgoritmer med lignende tidskompleksitet, for eksempel interpolasjonssøk eller eksponentielt søk.
  • Binært søk egner seg godt for å søke i store datasett som er lagret i eksternt minne, for eksempel på en harddisk eller i skyen.
  • Matrisen skal sorteres.
  • Binært søk krever at datastrukturen som søkes lagres i sammenhengende minneplasseringer.
  • Binært søk krever at elementene i matrisen er sammenlignbare, noe som betyr at de må kunne bestilles.

Ofte stilte spørsmål (FAQs) om binært søk:

1. Hva er binært søk?

Binært søk er en effektiv algoritme for å finne en målverdi innenfor en sortert matrise. Det fungerer ved å gjentatte ganger dele søkeintervallet i to.

2. Hvordan fungerer binært søk?

Binært søk sammenligner målverdien med det midterste elementet i matrisen. Hvis de er like, er søket vellykket. Hvis målet er mindre enn det midterste elementet, fortsetter søket i den nedre halvdelen av matrisen. Hvis målet er større, fortsetter søket i øvre halvdel. Denne prosessen gjentas til målet er funnet eller søkeintervallet er tomt.

int å doble

3. Hva er tidskompleksiteten til binært søk?

Tidskompleksiteten til binært søk er O(log2n), hvor n er antall elementer i matrisen. Dette er fordi størrelsen på søkeintervallet halveres i hvert trinn.

4. Hva er forutsetningene for binært søk?

Binært søk krever at matrisen er sortert i stigende eller synkende rekkefølge. Hvis matrisen ikke er sortert, kan vi ikke bruke binært søk til å søke etter et element i matrisen.

5. Hva skjer hvis matrisen ikke er sortert for binært søk?

Hvis matrisen ikke er sortert, kan binært søk gi feil resultater. Den er avhengig av matrisens sorterte natur for å ta avgjørelser om hvilken halvdel av matrisen som skal søkes.

6. Kan binærsøk brukes på ikke-numeriske data?

Ja, binært søk kan brukes på ikke-numeriske data så lenge det er en definert rekkefølge for elementene. Den kan for eksempel brukes til å søke etter strenger i alfabetisk rekkefølge.

7. Hva er noen vanlige ulemper med binært søk?

Ulempen med binært søk er at inndatamatrisen må sorteres for å avgjøre hvilken halvpart av målelementet som kan ligge. For usorterte matriser må vi derfor sortere matrisen før vi bruker binært søk.

8. Når bør binærsøk brukes?

Binært søk bør brukes når du søker etter en målverdi i en sortert matrise, spesielt når størrelsen på matrisen er stor. Det er spesielt effektivt for store datasett sammenlignet med lineære søkealgoritmer.

9. Kan binært søk implementeres rekursivt?

Ja, binært søk kan implementeres både iterativt og rekursivt. Den rekursive implementeringen fører ofte til mer konsis kode, men kan ha litt høyere overhead på grunn av rekursiv stabelplass eller funksjonskall.

10. Er binært søk alltid det beste valget for å søke i en sortert matrise?

Selv om binært søk er veldig effektivt for søk i sorterte arrays, kan det være spesifikke tilfeller der andre søkealgoritmer er mer hensiktsmessige, for eksempel når det er snakk om små datasett eller når arrayen ofte endres.

Relaterte artikler:

  • Binær søk på svar veiledning med problemer
  • Lineært søk vs binært søk
  • Hvordan identifisere og løse binære søkeproblemer?