logo

TechCodeview

Binární vyhledávací algoritmus – iterativní a rekurzivní implementace

Binární vyhledávání Algoritmus je vyhledávací algoritmus použit v seřazeném poli podle opakované dělení intervalu vyhledávání na polovinu . Myšlenkou binárního vyhledávání je využít informace, že pole je tříděno, a snížit časovou složitost na O(log N).

Binární vyhledávání je vyhledávací algoritmus používaný k nalezení pozice cílové hodnoty v a seřazeno pole. Funguje to tak, že se interval vyhledávání opakovaně dělí na polovinu, dokud není nalezena cílová hodnota nebo je interval prázdný. Interval vyhledávání se zkrátí na polovinu porovnáním cílového prvku se střední hodnotou prostoru vyhledávání.

sql klauzule

Chcete-li použít algoritmus binárního vyhledávání:



  • Struktura dat musí být tříděna.
  • Přístup k jakémukoli prvku datové struktury trvá konstantní čas.

Binární vyhledávací algoritmus:

V tomto algoritmu

  • Vyhledávací prostor rozdělte na dvě poloviny nalezení středního indexu uprostřed .

Nalezení středního indexu mid v binárním vyhledávacím algoritmu

  • Porovnejte střední prvek vyhledávacího prostoru s klíčem.
  • Pokud je klíč nalezen v prostředním prvku, proces je ukončen.
  • Pokud klíč není nalezen v prostředním prvku, vyberte, která polovina bude použita jako další vyhledávací prostor.
    • Pokud je klíč menší než prostřední prvek, pak se pro další vyhledávání použije levá strana.
    • Pokud je klíč větší než prostřední prvek, pak se pro další vyhledávání použije pravá strana.
  • Tento proces pokračuje, dokud není klíč nalezen nebo dokud není vyčerpán celkový vyhledávací prostor.

Jak funguje binární vyhledávací algoritmus?

Chcete-li porozumět fungování binárního vyhledávání, zvažte následující obrázek:

Zvažte pole arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} a cíl = 23 .

První krok: Vypočítejte střed a porovnejte středový prvek s klíčem. Pokud je klíč menší než střední prvek, posuňte se doleva a pokud je větší než střed, posuňte vyhledávací prostor doprava.

  • Klíč (tj. 23) je větší než aktuální střední prvek (tj. 16). Vyhledávací prostor se přesune doprava.

Binární vyhledávací algoritmus: Porovnejte klíč s 16

  • Klíč je menší než aktuální střední 56. Prostor pro vyhledávání se přesune doleva.

Binární vyhledávací algoritmus: Porovnejte klíč s 56

Druhý krok: Pokud klíč odpovídá hodnotě středního prvku, prvek je nalezen a hledání se zastaví.

Binární vyhledávací algoritmus: Klíč se shoduje se středem

Doporučený postup Binární vyhledávání Vyzkoušejte to!

The Binární vyhledávací algoritmus lze implementovat dvěma následujícími způsoby

  • Iterativní binární vyhledávací algoritmus
  • Rekurzivní binární vyhledávací algoritmus

Níže jsou uvedeny pseudokódy pro přístupy.

Iterativní binární vyhledávací algoritmus:

Zde pomocí smyčky while pokračujeme v procesu porovnávání klíče a rozdělení vyhledávacího prostoru na dvě poloviny.

Implementace iterativního binárního vyhledávacího 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; }>
Jáva 
// 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);  } }>
Krajta 
# 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>= low) { mid = low + Math.floor((vysoká - nízká) / 2);    // Pokud je prvek přítomen uprostřed // sám if (arr[mid] == x) return mid;    // Pokud je prvek menší než mid, pak // může být přítomen v levém podpole pouze tehdy, když (arr[mid]> x) high = mid - 1;    // Jinak může být prvek přítomen pouze // v pravém podpole else low = mid + 1;  } // Dostaneme se sem, když prvek není // přítomen v poli return -1; } arr =new Array(2, 3, 4, 10, 40);  x = 10;  n = arr.length;  vysledek = binarySearch(arr, x);   (výsledek == -1) ? console.log('Prvek není přítomen v poli') : console.log ('Prvek je přítomen na indexu ' + výsledek);   // Tento kód přispěli 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ýstup 
Element is present at index 3>

Časová náročnost: O(log N)
Pomocný prostor: O(1)

Rekurzivní binární vyhledávací algoritmus:

Vytvořte rekurzivní funkci a porovnejte střed vyhledávacího prostoru s klíčem. A na základě výsledku buď vraťte index, kde je klíč nalezen, nebo zavolejte rekurzivní funkci pro další vyhledávací prostor.

proč řetězec neměnný v java

Implementace rekurzivního binárního vyhledávacího 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ízká) { int střední = nízká + (vysoká - nízká) / 2;  // Pokud je prvek přítomen uprostřed // sám if (arr[mid] == x) return mid;  // Pokud je prvek menší než mid, pak // může být přítomen pouze v levém podpole if (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Jinak může být prvek přítomen pouze // v pravém podpole return binarySearch(arr, mid + 1, high, x);  } } // Kód ovladače int main() { int arr[] = { 2, 3, 4, 10, 40 };  int dotaz = 10;  int n = sizeof(arr) / sizeof(arr[0]);  int vysledek = binarySearch(arr, 0, n - 1, dotaz);  (výsledek == -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ízká) { int střední = nízká + (vysoká - nízká) / 2;  // Pokud je prvek přítomen uprostřed // sám if (arr[mid] == x) return mid;  // Pokud je prvek menší než mid, pak // může být přítomen pouze v levém podpole if (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Jinak může být prvek přítomen pouze // v pravém podpole return binarySearch(arr, mid + 1, high, x);  } // Dostaneme se sem, když prvek není // přítomen v poli return -1; } // Kód ovladače int main() { int arr[] = { 2, 3, 4, 10, 40 };  int n = sizeof(arr) / sizeof(arr[0]);  int x = 10;  int vysledek = binarySearch(arr, 0, n - 1, x);  (výsledek == -1) ? printf('Prvek není přítomen v poli') : printf('Prvek je přítomen na indexu %d', výsledek);  návrat 0; }>
Jáva 
// 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ízká) { int střední = nízká + (vysoká - nízká) / 2;  // Pokud je prvek přítomen v // samotném středu if (arr[mid] == x) return mid;  // Pokud je prvek menší než mid, pak // může být přítomen pouze v levém podpole if (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Jinak může být prvek přítomen pouze // v pravém podpole return binarySearch(arr, mid + 1, high, x);  } // Dostaneme se sem, když prvek není přítomen // v poli return -1;  } // Kód ovladače 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 vysledek = ob.binarySearch(arr, 0, n - 1, x);  if (výsledek == -1) System.out.println( 'Prvek není v poli přítomen');  else System.out.println( 'Prvek je přítomen na indexu ' + výsledek);  } } /* Tento kód přispěl Rajat Mishra */>
Krajta 
# 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 # Pokud je prvek přítomen přímo uprostřed if arr[mid] == x: return mid # Pokud je prvek menší než střední, pak # může být přítomen pouze v levém podpole elif arr[mid]> x: return binarySearch(arr, low, mid-1, x) # Jinak prvek může být přítomen pouze # v pravém podpole else: return binarySearch(arr, mid + 1, high, x ) # Element není přítomen v poli else: return -1 # Driver Code if __name__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # Výsledek volání funkce = binarySearch( arr, 0, len(arr)-1, x) pokud výsledek != -1: print('Prvek je přítomen na indexu', výsledek) else: print('Prvek není přítomen 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ízká) { int střední = nízká + (vysoká - nízká) / 2;  // Pokud je prvek přítomen v // samotném středu if (arr[mid] == x) return mid;  // Pokud je prvek menší než mid, pak // může být přítomen pouze v levém podpole if (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Jinak může být prvek přítomen pouze // v pravém podpole return binarySearch(arr, mid + 1, high, x);  } // Dostaneme se sem, když prvek není přítomen // v poli return -1;  } // Kód ovladače public static void Main() { int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.Length;  int x = 10;  int vysledek = binarySearch(arr, 0, n - 1, x);  if (výsledek == -1) Console.WriteLine( 'Prvek není přítomen v arrau');  else Console.WriteLine('Prvek je přítomen na indexu ' + výsledek);  } } // Tento kód přispěl 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>= low) { let mid = low + Math.floor((vysoká - nízká) / 2);  // Pokud je prvek přítomen uprostřed // sám if (arr[mid] == x) return mid;  // Pokud je prvek menší než mid, pak // může být přítomen pouze v levém podpole if (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Jinak může být prvek přítomen pouze // v pravém podpole return binarySearch(arr, mid + 1, high, x);  } // Dostaneme se sem, když prvek není // přítomen v poli return -1; } nechť arr = [ 2, 3, 4, 10, 40 ]; nechť x = 10; let n = arr.length let result = binarySearch(arr, 0, n - 1, x); (výsledek == -1) ? console.log( 'Prvek není přítomen v poli') : console.log('Prvek je přítomen na indexu ' +výsledek);>
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ízký) { $střed = ceil($nízký + ($vysoký - $nízký) / 2); // Pokud je prvek přítomen // v samotném středu if ($arr[$mid] == $x) return floor($mid); // Pokud je prvek menší než // mid, pak může být // přítomen v levém dílčím poli pouze tehdy, když ($arr[$mid]> $x) return binarySearch($arr, $low, $mid - 1, $x ); // Jinak může být prvek // přítomen pouze v pravém podpole return binarySearch($arr, $mid + 1, $high, $x); } // Dostaneme se sem, když prvek // není přítomen v poli return -1; } // Kód ovladače $arr = array(2, 3, 4, 10, 40); $n = počet($arr); $x = 10; $vysledek = binarySearch($arr, 0, $n - 1, $x); if(($result == -1)) echo 'Prvek není v poli přítomen'; else echo 'Prvek je přítomen na indexu ', $výsledek; ?>>
Výstup 
Element is present at index 3>
  • Časová náročnost:
    • Nejlepší případ: O(1)
    • Průměrný případ: O (log N)
    • Nejhorší případ: O (log N)
  • Pomocný prostor: O(1), je-li uvažován zásobník rekurzivních volání, bude pomocný prostor O(logN).
  • Binární vyhledávání lze použít jako stavební kámen pro složitější algoritmy používané ve strojovém učení, jako jsou algoritmy pro trénování neuronových sítí nebo hledání optimálních hyperparametrů pro model.
  • Může být použit pro vyhledávání v počítačové grafice, jako jsou algoritmy pro sledování paprsků nebo mapování textur.
  • Lze jej použít pro vyhledávání v databázi.
  • Binární vyhledávání je rychlejší než lineární, zejména u velkých polí.
  • Efektivnější než jiné vyhledávací algoritmy s podobnou časovou složitostí, jako je interpolační vyhledávání nebo exponenciální vyhledávání.
  • Binární vyhledávání se dobře hodí pro vyhledávání velkých datových sad, které jsou uloženy v externí paměti, například na pevném disku nebo v cloudu.
  • Pole by mělo být seřazeno.
  • Binární vyhledávání vyžaduje, aby prohledávaná datová struktura byla uložena v souvislých paměťových místech.
  • Binární vyhledávání vyžaduje, aby prvky pole byly srovnatelné, což znamená, že musí být možné je seřadit.

Často kladené otázky (FAQ) o binárním vyhledávání:

1. Co je binární vyhledávání?

Binární vyhledávání je účinný algoritmus pro nalezení cílové hodnoty v seřazeném poli. Funguje to tak, že se interval vyhledávání opakovaně dělí na polovinu.

2. Jak funguje binární vyhledávání?

Binární vyhledávání porovnává cílovou hodnotu se středním prvkem pole. Pokud jsou stejné, je hledání úspěšné. Pokud je cíl menší než prostřední prvek, vyhledávání pokračuje v dolní polovině pole. Pokud je cíl větší, pokračuje hledání v horní polovině. Tento proces se opakuje, dokud není nalezen cíl nebo dokud není interval hledání prázdný.

3. Jaká je časová složitost binárního vyhledávání?

Časová složitost binárního vyhledávání je O(log2n), kde n je počet prvků v poli. Je to proto, že velikost intervalu vyhledávání je v každém kroku poloviční.

4. Jaké jsou předpoklady pro binární vyhledávání?

Binární vyhledávání vyžaduje, aby bylo pole řazeno vzestupně nebo sestupně. Pokud pole není seřazeno, nemůžeme použít binární vyhledávání k vyhledání prvku v poli.

5. Co se stane, pokud pole není seřazeno pro binární vyhledávání?

Pokud pole není seřazeno, může binární vyhledávání vrátit nesprávné výsledky. Při rozhodování o tom, kterou polovinu pole prohledat, spoléhá na seřazenou povahu pole.

6. Lze binární vyhledávání použít na nečíselná data?

Ano, binární vyhledávání lze použít na nečíselná data, pokud existuje definované pořadí prvků. Lze jej například použít k vyhledávání řetězců v abecedním pořadí.

7. Jaké jsou některé běžné nevýhody binárního vyhledávání?

Nevýhodou Binary Search je, že vstupní pole je potřeba třídit, aby se rozhodlo, ve které polovině může ležet cílový prvek. Proto u netříděných polí musíme před použitím binárního vyhledávání pole seřadit.

8. Kdy by se mělo použít binární vyhledávání?

Binární vyhledávání by se mělo používat při hledání cílové hodnoty v seřazeném poli, zvláště když je velikost pole velká. Ve srovnání s lineárními vyhledávacími algoritmy je zvláště efektivní pro velké soubory dat.

9. Lze binární vyhledávání implementovat rekurzivně?

Ano, binární vyhledávání lze implementovat iterativně i rekurzivně. Rekurzivní implementace často vede ke stručnějšímu kódu, ale může mít mírně vyšší režii kvůli rekurzivnímu zásobníku nebo volání funkcí.

10. Je binární vyhledávání vždy nejlepší volbou pro vyhledávání v seřazeném poli?

Zatímco binární vyhledávání je velmi efektivní pro vyhledávání v setříděných polích, mohou nastat specifické případy, kdy jsou vhodnější jiné vyhledávací algoritmy, například když se jedná o malé datové sady nebo když je pole často upravováno.

Související články:

  • Binární vyhledávání v odpovědi na tutoriál s problémy
  • Lineární vyhledávání vs binární vyhledávání
  • Jak identifikovat a řešit problémy s binárním vyhledáváním?