logo

TechCodeview

Binárny vyhľadávací algoritmus – iteratívna a rekurzívna implementácia

Binárne vyhľadávanie Algoritmus je a vyhľadávací algoritmus použité v zoradenom poli podľa opakovaným delením intervalu vyhľadávania na polovicu . Myšlienkou binárneho vyhľadávania je použiť informáciu, že pole je triedené a znížiť časovú zložitosť na O(log N).

Binárne vyhľadávanie je vyhľadávací algoritmus používaný na nájdenie pozície cieľovej hodnoty v rámci a triedené pole. Funguje to tak, že interval vyhľadávania sa opakovane delí na polovicu, kým sa nenájde cieľová hodnota alebo kým nebude interval prázdny. Interval vyhľadávania sa zníži na polovicu porovnaním cieľového prvku so strednou hodnotou priestoru vyhľadávania.

kandidátsky kľúč

Ak chcete použiť algoritmus binárneho vyhľadávania:



  • Štruktúra údajov musí byť triedená.
  • Prístup k akémukoľvek prvku dátovej štruktúry trvá konštantne.

Binárny vyhľadávací algoritmus:

V tomto algoritme,

  • Hľadaný priestor rozdeľte na dve polovice nájdenie stredného indexu stred .

Nájdenie stredného indexu uprostred v binárnom vyhľadávacom algoritme

  • Porovnajte stredný prvok vyhľadávacieho priestoru s kľúčom.
  • Ak sa kľúč nájde v strednom prvku, proces sa ukončí.
  • Ak kľúč nenájdete v strednom prvku, vyberte, ktorá polovica sa použije ako ďalší vyhľadávací priestor.
    • Ak je kľúč menší ako stredný prvok, na ďalšie vyhľadávanie sa použije ľavá strana.
    • Ak je kľúč väčší ako stredný prvok, na ďalšie vyhľadávanie sa použije pravá strana.
  • Tento proces pokračuje, kým sa nenájde kľúč alebo kým sa nevyčerpá celý priestor na vyhľadávanie.

Ako funguje binárny vyhľadávací algoritmus?

Aby ste pochopili fungovanie binárneho vyhľadávania, zvážte nasledujúci obrázok:

Zvážte pole arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} , a Cieľ = 23 .

Prvý krok: Vypočítajte stred a porovnajte stredný prvok s kľúčom. Ak je kľúč menší ako stred prvku, posuňte sa doľava a ak je väčší ako stred, posuňte priestor vyhľadávania doprava.

  • Kľúč (t. j. 23) je väčší ako aktuálny stredný prvok (t. j. 16). Priestor vyhľadávania sa presunie doprava.

Binárny vyhľadávací algoritmus: Porovnajte kľúč so 16

  • Kľúč je menší ako aktuálny stred 56. Priestor vyhľadávania sa presunie doľava.

Binárny vyhľadávací algoritmus: Porovnajte kľúč s 56

Druhý krok: Ak sa kľúč zhoduje s hodnotou stredného prvku, prvok sa nájde a vyhľadávanie sa zastaví.

Binárny vyhľadávací algoritmus: Kľúčové zhody so stredom

Odporúčaný postup Binárne vyhľadávanie Vyskúšajte to!

The Binárny vyhľadávací algoritmus možno implementovať nasledujúcimi dvoma spôsobmi

  • Iteračný binárny vyhľadávací algoritmus
  • Rekurzívny binárny vyhľadávací algoritmus

Nižšie sú uvedené pseudokódy pre prístupy.

Iteračný binárny vyhľadávací algoritmus:

Tu používame slučku while na pokračovanie v procese porovnávania kľúča a rozdelenia vyhľadávacieho priestoru na dve polovice.

Implementácia iteratívneho binárneho vyhľadávacieho algoritmu:

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>= nízka) { stredná = nízka + Math.floor((vysoká - nízka) / 2);    // Ak je prvok prítomný v strede // sám if (arr[mid] == x) return mid;    // Ak je prvok menší ako stred, // môže byť prítomný iba v ľavom podpole, ak (arr[mid]> x) high = mid - 1;    // V opačnom prípade môže byť prvok prítomný iba // v pravom podpole else low = mid + 1;  } // Dostaneme sa sem, keď prvok nie je // prítomný v poli return -1; } arr =new Array(2, 3, 4, 10, 40);  x = 10;  n = arr.dĺžka;  vysledok = binarySearch(arr, x);   (výsledok == -1) ? console.log('Prvok nie je prítomný v poli') : console.log ('Prvok je prítomný v indexe ' + výsledok);   // Tento kód prispeli simranarora5sos a 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. ?>>
Výkon 
Element is present at index 3>

Časová zložitosť: O (log N)
Pomocný priestor: O(1)

Rekurzívny binárny vyhľadávací algoritmus:

Vytvorte rekurzívnu funkciu a porovnajte stred vyhľadávacieho priestoru s kľúčom. A na základe výsledku buď vráťte index, kde sa kľúč nachádza, alebo zavolajte rekurzívnu funkciu pre ďalší vyhľadávací priestor.

Implementácia rekurzívneho binárneho vyhľadávacieho algoritmu:

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>= nízka) { int stredná = nízka + (vysoká - nízka) / 2;  // Ak je prvok prítomný v strede // sám if (arr[mid] == x) return mid;  // Ak je prvok menší ako stred, potom // môže byť prítomný iba v ľavom podpole if (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // V opačnom prípade môže byť prvok prítomný iba // v pravom podpole return binarySearch(arr, mid + 1, high, x);  } } // Kód ovládača int main() { int arr[] = { 2, 3, 4, 10, 40 };  int dotaz = 10;  int n = sizeof(arr) / sizeof(arr[0]);  int vysledok = binarySearch(arr, 0, n - 1, dotaz);  (výsledok == -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>= nízka) { int stredná = nízka + (vysoká - nízka) / 2;  // Ak je prvok prítomný v strede // sám if (arr[mid] == x) return mid;  // Ak je prvok menší ako stred, potom // môže byť prítomný iba v ľavom podpole if (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // V opačnom prípade môže byť prvok prítomný iba // v pravom podpole return binarySearch(arr, mid + 1, high, x);  } // Dostaneme sa sem, keď prvok nie je // prítomný v poli return -1; } // Kód ovládača int main() { int arr[] = { 2, 3, 4, 10, 40 };  int n = sizeof(arr) / sizeof(arr[0]);  int x = 10;  int vysledok = binarySearch(arr, 0, n - 1, x);  (výsledok == -1) ? printf('Prvok nie je prítomný v poli') : printf('Prvok je prítomný na indexe %d', výsledok);  návrat 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>= nízka) { int stredná = nízka + (vysoká - nízka) / 2;  // Ak je prvok prítomný v // strede samotnom if (arr[mid] == x) return mid;  // Ak je prvok menší ako stred, potom // môže byť prítomný iba v ľavom podpole if (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // V opačnom prípade môže byť prvok prítomný iba // v pravom podpole return binarySearch(arr, mid + 1, high, x);  } // Dostaneme sa sem, keď prvok nie je prítomný // v poli return -1;  } // Kód ovládača 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 vysledok = ob.binarySearch(arr, 0, n - 1, x);  if (výsledok == -1) System.out.println( 'Prvok nie je prítomný v poli');  else System.out.println( 'Prvok je prítomný v indexe ' + výsledok);  } } /* Tento kód prispel 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>= low: mid = low + (high - low) // 2 # Ak je prvok prítomný v samotnom strede if arr[mid] == x: return mid # Ak je prvok menší ako stred, potom # môže byť prítomný iba v ľavom podpole elif arr[mid]> x: return binarySearch(arr, low, mid-1, x) # Inak prvok môže byť prítomný iba # v pravom podpole else: return binarySearch(arr, mid + 1, high, x ) # Element nie je prítomný v poli else: return -1 # Driver Code if __name__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # Výsledok volania funkcie = binarySearch( arr, 0, len(arr)-1, x) ak výsledok != -1: print('Prvok je prítomný na indexe', výsledok) else: print('Prvok nie je prítomný v poli')>
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>= nízka) { int stredná = nízka + (vysoká - nízka) / 2;  // Ak je prvok prítomný v // strede samotnom if (arr[mid] == x) return mid;  // Ak je prvok menší ako stred, potom // môže byť prítomný iba v ľavom podpole if (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // V opačnom prípade môže byť prvok prítomný iba // v pravom podpole return binarySearch(arr, mid + 1, high, x);  } // Dostaneme sa sem, keď prvok nie je prítomný // v poli return -1;  } // Kód ovládača public static void Main() { int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.Dlzka;  int x = 10;  int vysledok = binarySearch(arr, 0, n - 1, x);  if (výsledok == -1) Console.WriteLine( 'Prvok nie je prítomný v arrau');  else Console.WriteLine('Prvok je prítomný v indexe ' + výsledok);  } } // Tento kód prispel 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>= nízka) { nech stredná = nízka + Math.floor((vysoká - nízka) / 2);  // Ak je prvok prítomný v strede // sám if (arr[mid] == x) return mid;  // Ak je prvok menší ako stred, potom // môže byť prítomný iba v ľavom podpole if (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // V opačnom prípade môže byť prvok prítomný iba // v pravom podpole return binarySearch(arr, mid + 1, high, x);  } // Dostaneme sa sem, keď prvok nie je // prítomný v poli return -1; } nech arr = [ 2, 3, 4, 10, 40]; nech x = 10; nech n = arr.length nech vysledok = binarySearch(arr, 0, n - 1, x); (výsledok == -1) ? console.log( 'Prvok nie je prítomný v poli') : console.log('Prvok je prítomný v indexe ' +výsledok);>
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>= $nízky) { $stred = ceil($nízky + ($vysoký - $nízky) / 2); // Ak je prvok prítomný // v samotnom strede if ($arr[$mid] == $x) return floor($mid); // Ak je prvok menší ako // mid, potom môže byť // prítomný v ľavom podpole iba vtedy, ak ($arr[$mid]> $x) return binarySearch($arr, $low, $mid - 1, $x ); // V opačnom prípade môže byť prvok // prítomný iba v pravom podpole return binarySearch($arr, $mid + 1, $high, $x); } // Dostaneme sa sem, keď prvok // nie je prítomný v poli return -1; } // Kód ovládača $arr = array(2, 3, 4, 10, 40); $n = pocet($arr); $x = 10; $vysledok = binarySearch($arr, 0, $n - 1, $x); if(($výsledok == -1)) echo 'Prvok nie je prítomný v poli'; else echo 'Prvok je prítomný na indexe ', $výsledok; ?>>
Výkon 
Element is present at index 3>
  • Časová zložitosť:
    • Najlepší prípad: O(1)
    • Priemerný prípad: O (log N)
    • Najhorší prípad: O (log N)
  • Pomocný priestor: O(1), Ak sa berie do úvahy zásobník rekurzívnych hovorov, pomocný priestor bude O(logN).
  • Binárne vyhľadávanie môže byť použité ako stavebný kameň pre zložitejšie algoritmy používané v strojovom učení, ako sú algoritmy na trénovanie neurónových sietí alebo hľadanie optimálnych hyperparametrov pre model.
  • Dá sa použiť na vyhľadávanie v počítačovej grafike, ako sú algoritmy na sledovanie lúčov alebo mapovanie textúr.
  • Dá sa použiť na vyhľadávanie v databáze.
  • Binárne vyhľadávanie je rýchlejšie ako lineárne, najmä pri veľkých poliach.
  • Efektívnejšie ako iné vyhľadávacie algoritmy s podobnou časovou zložitosťou, ako je interpolačné vyhľadávanie alebo exponenciálne vyhľadávanie.
  • Binárne vyhľadávanie je vhodné na vyhľadávanie veľkých množín údajov, ktoré sú uložené v externej pamäti, napríklad na pevnom disku alebo v cloude.
  • Pole by malo byť zoradené.
  • Binárne vyhľadávanie vyžaduje, aby bola vyhľadávaná dátová štruktúra uložená v súvislých pamäťových miestach.
  • Binárne vyhľadávanie vyžaduje, aby boli prvky poľa porovnateľné, čo znamená, že sa musia dať zoradiť.

Často kladené otázky (FAQ) o binárnom vyhľadávaní:

1. Čo je binárne vyhľadávanie?

Binárne vyhľadávanie je efektívny algoritmus na nájdenie cieľovej hodnoty v rámci triedeného poľa. Funguje to tak, že interval vyhľadávania sa opakovane delí na polovicu.

2. Ako funguje binárne vyhľadávanie?

Binárne vyhľadávanie porovnáva cieľovú hodnotu so stredným prvkom poľa. Ak sú rovnaké, hľadanie je úspešné. Ak je cieľ menší ako stredný prvok, vyhľadávanie pokračuje v dolnej polovici poľa. Ak je cieľ väčší, hľadanie pokračuje v hornej polovici. Tento proces sa opakuje, kým sa nenájde cieľ alebo kým sa nevyprázdni vyhľadávací interval.

3. Aká je časová zložitosť binárneho vyhľadávania?

Časová zložitosť binárneho vyhľadávania je O(log2n), kde n je počet prvkov v poli. Je to spôsobené tým, že veľkosť vyhľadávacieho intervalu sa v každom kroku znižuje na polovicu.

4. Aké sú predpoklady pre binárne vyhľadávanie?

Binárne vyhľadávanie vyžaduje, aby bolo pole zoradené vzostupne alebo zostupne. Ak pole nie je zoradené, nemôžeme použiť binárne vyhľadávanie na vyhľadávanie prvku v poli.

5. Čo sa stane, ak pole nie je zoradené pre binárne vyhľadávanie?

Ak pole nie je zoradené, binárne vyhľadávanie môže vrátiť nesprávne výsledky. Pri rozhodovaní o tom, ktorá polovica poľa sa má prehľadávať, sa spolieha na triedenú povahu poľa.

6. Dá sa binárne vyhľadávanie použiť na nečíselné údaje?

Áno, binárne vyhľadávanie je možné použiť na nečíselné údaje, pokiaľ existuje definované poradie prvkov. Môže sa použiť napríklad na vyhľadávanie reťazcov v abecednom poradí.

kontrola java je nulová

7. Aké sú niektoré bežné nevýhody binárneho vyhľadávania?

Nevýhodou binárneho vyhľadávania je, že vstupné pole je potrebné triediť, aby sa rozhodlo, v ktorej polovici môže ležať cieľový prvok. Preto v prípade nezoradených polí musíme pred použitím binárneho vyhľadávania zoradiť pole.

8. Kedy by sa malo použiť binárne vyhľadávanie?

Binárne vyhľadávanie by sa malo použiť pri hľadaní cieľovej hodnoty v zoradenom poli, najmä ak je veľkosť poľa veľká. V porovnaní s lineárnymi vyhľadávacími algoritmami je obzvlášť účinný pre veľké súbory údajov.

9. Môže byť binárne vyhľadávanie implementované rekurzívne?

Áno, binárne vyhľadávanie je možné implementovať iteratívne aj rekurzívne. Rekurzívna implementácia často vedie k stručnejšiemu kódu, ale môže mať o niečo vyššiu réžiu v dôsledku rekurzívneho zásobníkového priestoru alebo volaní funkcií.

10. Je binárne vyhľadávanie vždy tou najlepšou voľbou na vyhľadávanie v triedenom poli?

Zatiaľ čo binárne vyhľadávanie je veľmi efektívne na vyhľadávanie v triedených poliach, môžu nastať špecifické prípady, kedy sú vhodnejšie iné vyhľadávacie algoritmy, ako napríklad pri práci s malými množinami údajov alebo keď sa pole často upravuje.

Súvisiace články:

  • Binary Search on Answer Tutorial with Problems
  • Lineárne vyhľadávanie vs binárne vyhľadávanie
  • Ako identifikovať a vyriešiť problémy s binárnym vyhľadávaním?