logo

TechCodeview

Algorytm wyszukiwania binarnego – implementacja iteracyjna i rekurencyjna

Wyszukiwanie binarne Algorytm jest algorytm wyszukiwania używane w tablicy posortowanej według wielokrotne dzielenie interwału wyszukiwania na pół . Ideą wyszukiwania binarnego jest wykorzystanie informacji o posortowaniu tablicy i zredukowanie złożoności czasowej do O(log N).

Wyszukiwanie binarne to algorytm wyszukiwania używany do znalezienia pozycji wartości docelowej w obrębie a posortowane szyk. Działa poprzez wielokrotne dzielenie interwału wyszukiwania na pół, aż do znalezienia wartości docelowej lub interwału będzie pusty. Interwał wyszukiwania zmniejsza się o połowę poprzez porównanie elementu docelowego ze środkową wartością przestrzeni poszukiwań.



inurl:.git/head

Aby zastosować algorytm wyszukiwania binarnego:

  • Struktura danych musi być posortowana.
  • Dostęp do dowolnego elementu struktury danych zajmuje stały czas.

Algorytm wyszukiwania binarnego:

W tym algorytmie

  • Podziel przestrzeń poszukiwań na dwie połowy według znalezienie środkowego indeksu mid .

Znalezienie środkowego indeksu w algorytmie wyszukiwania binarnego



  • Porównaj środkowy element przestrzeni poszukiwań z kluczem.
  • Jeśli klucz zostanie znaleziony w środkowym elemencie, proces zostanie zakończony.
  • Jeśli klucz nie zostanie znaleziony w środkowym elemencie, wybierz, która połowa będzie używana jako następna przestrzeń wyszukiwania.
    • Jeśli klucz jest mniejszy niż środkowy element, wówczas do kolejnego wyszukiwania używana jest lewa strona.
    • Jeśli klucz jest większy niż środkowy element, wówczas do kolejnego wyszukiwania wykorzystywana jest prawa strona.
  • Proces ten jest kontynuowany do momentu znalezienia klucza lub wyczerpania całej przestrzeni poszukiwań.

Jak działa algorytm wyszukiwania binarnego?

Aby zrozumieć działanie wyszukiwania binarnego, rozważ poniższą ilustrację:

Rozważ tablicę tablica [] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} , oraz cel = 23 .

Pierwszy krok: Oblicz środek i porównaj środkowy element z kluczem. Jeśli klucz jest mniejszy niż środkowy element, przesuń w lewo, a jeśli jest większy niż środkowy, przesuń przestrzeń wyszukiwania w prawo.



  • Klucz (tj. 23) jest większy niż bieżący środkowy element (tj. 16). Przestrzeń poszukiwań przesuwa się w prawo.

Algorytm wyszukiwania binarnego: porównaj klucz z 16

  • Klucz jest mniejszy niż bieżący środek 56. Przestrzeń wyszukiwania przesuwa się w lewo.

Algorytm wyszukiwania binarnego: porównaj klucz z 56

Drugi krok: Jeśli klucz odpowiada wartości środkowego elementu, element zostanie znaleziony i zatrzymanie wyszukiwania.

Algorytm wyszukiwania binarnego: Kluczowe dopasowania ze środkiem

Zalecana praktyka Wyszukiwanie binarne Wypróbuj!

The Algorytm wyszukiwania binarnego można wdrożyć na dwa poniższe sposoby

  • Iteracyjny algorytm wyszukiwania binarnego
  • Algorytm rekurencyjnego wyszukiwania binarnego

Poniżej podano pseudokody podejść.

Iteracyjny algorytm wyszukiwania binarnego:

Tutaj używamy pętli while, aby kontynuować proces porównywania klucza i dzielenia przestrzeni poszukiwań na dwie połowy.

Implementacja iteracyjnego algorytmu wyszukiwania binarnego:

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; }>
Jawa 
// 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);  } }>
Pyton 
# 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>= niski) { średni = niski + Math.floor((wysoki - niski) / 2);    // Jeśli element znajduje się w środku // sam if (arr[mid] == x) return mid;    // Jeśli element jest mniejszy niż mid, to // może występować w lewej podtablicy tylko wtedy, gdy (arr[mid]> x) high = mid - 1;    // W przeciwnym razie element może występować tylko // w prawej podtablicy, w przeciwnym razie low = mid + 1;  } // Docieramy tutaj, gdy element // nie jest obecny w tablicy return -1; } arr =nowa tablica(2, 3, 4, 10, 40);  x = 10;  n = długość tablicy;  wynik = binarySearch(arr, x);   (wynik == -1)? console.log('Element nie występuje w tablicy') : console.log ('Element występuje w indeksie ' + wynik);   // Ten kod został napisany przez simranarora5sos i 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. ?>>
Wyjście 
Element is present at index 3>

Złożoność czasowa: O(log N)
Przestrzeń pomocnicza: O(1)

Algorytm rekurencyjnego wyszukiwania binarnego:

Utwórz funkcję rekurencyjną i porównaj środek przestrzeni poszukiwań z kluczem. Na podstawie wyniku albo zwróć indeks, w którym znaleziono klucz, albo wywołaj funkcję rekurencyjną dla następnej przestrzeni wyszukiwania.

Implementacja rekurencyjnego algorytmu wyszukiwania binarnego:

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>= niski) { int średni = niski + (wysoki - niski) / 2;  // Jeśli element znajduje się w środku // sam if (arr[mid] == x) return mid;  // Jeśli element jest mniejszy niż średni, to // może występować w lewej podtablicy tylko if (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // W przeciwnym razie element może występować tylko // w prawej podtablicy return binarySearch(arr, mid + 1, high, x);  } } // Kod sterownika int main() { int arr[] = { 2, 3, 4, 10, 40 };  int zapytanie = 10;  int n = rozmiar(tablica) / rozmiar(tablica[0]);  int wynik = binarySearch(arr, 0, n - 1, zapytanie);  (wynik == -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>= niski) { int średni = niski + (wysoki - niski) / 2;  // Jeśli element znajduje się w środku // sam if (arr[mid] == x) return mid;  // Jeśli element jest mniejszy niż średni, to // może występować w lewej podtablicy tylko if (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // W przeciwnym razie element może występować tylko // w prawej podtablicy return binarySearch(arr, mid + 1, high, x);  } // Docieramy tutaj, gdy element // nie jest obecny w tablicy return -1; } // Kod sterownika int main() { int arr[] = { 2, 3, 4, 10, 40 };  int n = rozmiar(tablica) / rozmiar(tablica[0]);  int x = 10;  int wynik = binarySearch(arr, 0, n - 1, x);  (wynik == -1)? printf('Element nie występuje w tablicy'): printf('Element występuje pod indeksem %d', wynik);  zwróć 0; }>
Jawa 
// 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>= niski) { int średni = niski + (wysoki - niski) / 2;  // Jeśli element znajduje się w // środku if (arr[mid] == x) return mid;  // Jeśli element jest mniejszy niż średni, to // może występować w lewej podtablicy tylko if (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // W przeciwnym razie element może występować tylko // w prawej podtablicy return binarySearch(arr, mid + 1, high, x);  } // Docieramy tutaj, gdy elementu nie ma // w tablicy return -1;  } // Kod sterownika public static void main(String args[]) { BinarySearch ob = new BinarySearch();  int tablica [] = { 2, 3, 4, 10, 40 };  int n = długość tablicy;  int x = 10;  int wynik = ob.binarySearch(arr, 0, n - 1, x);  if (wynik == -1) System.out.println( 'Element nie występuje w tablicy');  else System.out.println( 'Element znajduje się w indeksie ' + wynik);  } } /* Autorem tego kodu jest Rajat Mishra */>
Pyton 
# 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 # Jeśli element jest obecny w samym środku if arr[mid] == x: return mid # Jeśli element jest mniejszy niż środek, to # może być obecny tylko w lewej podtablicy elif arr[mid]> x: return binarySearch(arr, low, mid-1, x) # W innym przypadku element może występować tylko # w prawej podtablicy else: return binarySearch(arr, mid + 1, high, x ) # Elementu nie ma w tablicy else: return -1 # Kod sterownika if __name__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # Wynik wywołania funkcji = binarySearch( arr, 0, len(arr)-1, x) if wynik != -1: print('Element występuje w indeksie', wynik) else: print('Element nie występuje w tablicy')>
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>= niski) { int średni = niski + (wysoki - niski) / 2;  // Jeśli element znajduje się w // środku if (arr[mid] == x) return mid;  // Jeśli element jest mniejszy niż średni, to // może występować w lewej podtablicy tylko if (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // W przeciwnym razie element może występować tylko // w prawej podtablicy return binarySearch(arr, mid + 1, high, x);  } // Docieramy tutaj, gdy elementu nie ma // w tablicy return -1;  } // Kod sterownika public static void Main() { int[] arr = { 2, 3, 4, 10, 40 };  int n = tablica.Długość;  int x = 10;  int wynik = binarySearch(arr, 0, n - 1, x);  if (wynik == -1) Console.WriteLine( 'Element nie istnieje w tablicy');  else Console.WriteLine('Element znajduje się w indeksie ' + wynik);  } } // Ten kod został napisany przez 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>= niski) { niech średni = niski + Math.floor((wysoki - niski) / 2);  // Jeśli element znajduje się w środku // sam if (arr[mid] == x) return mid;  // Jeśli element jest mniejszy niż średni, to // może występować w lewej podtablicy tylko if (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // W przeciwnym razie element może występować tylko // w prawej podtablicy return binarySearch(arr, mid + 1, high, x);  } // Docieramy tutaj, gdy element // nie jest obecny w tablicy return -1; } niech arr = [ 2, 3, 4, 10, 40 ]; niech x = 10; niech n = długość tablicy niech wynik = binarySearch(arr, 0, n - 1, x); (wynik == -1)? console.log( 'Element nie występuje w tablicy'): console.log('Element występuje w indeksie ' +result);>
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>= $niski) { $mid = ceil($niski + ($wysoki - $niski) / 2); // Jeśli element jest obecny // w samym środku if ($arr[$mid] == $x) return Floor($mid); // Jeśli element jest mniejszy niż // mid, to może być // obecny w lewej podtablicy tylko wtedy, gdy ($arr[$mid]> $x) return binarySearch($arr, $low, $mid - 1, $x ); // W przeciwnym razie element może // występować tylko w prawej podtablicy return binarySearch($arr, $mid + 1, $high, $x); } // Docieramy tutaj, gdy element // nie występuje w tablicy return -1; } // Kod sterownika $arr = array(2, 3, 4, 10, 40); $n = liczba($arr); $x = 10; $result = binarySearch($arr, 0, $n - 1, $x); if(($result == -1)) echo 'Element nie występuje w tablicy'; else echo 'Element znajduje się w indeksie ', $result; ?>>
Wyjście 
Element is present at index 3>
  • Złożoność czasowa:
    • Najlepszy przypadek: O(1)
    • Średni przypadek: O(log N)
    • Najgorszy przypadek: O(log N)
  • Przestrzeń pomocnicza: O(1). Jeśli uwzględniony zostanie stos wywołań rekurencyjnych, wówczas przestrzeń pomocnicza będzie wynosić O(logN).
  • Wyszukiwanie binarne może służyć jako element składowy bardziej złożonych algorytmów stosowanych w uczeniu maszynowym, takich jak algorytmy do uczenia sieci neuronowych lub znajdowania optymalnych hiperparametrów dla modelu.
  • Można go wykorzystać do wyszukiwania w grafice komputerowej, np. w algorytmach śledzenia promieni czy mapowaniu tekstur.
  • Można go używać do przeszukiwania bazy danych.
  • Wyszukiwanie binarne jest szybsze niż wyszukiwanie liniowe, szczególnie w przypadku dużych tablic.
  • Bardziej wydajne niż inne algorytmy wyszukiwania o podobnej złożoności czasowej, takie jak wyszukiwanie interpolacyjne lub wyszukiwanie wykładnicze.
  • Wyszukiwanie binarne doskonale nadaje się do przeszukiwania dużych zbiorów danych przechowywanych w pamięci zewnętrznej, na przykład na dysku twardym lub w chmurze.
  • Tablicę należy posortować.
  • Wyszukiwanie binarne wymaga, aby przeszukiwana struktura danych była przechowywana w sąsiadujących lokalizacjach pamięci.
  • Wyszukiwanie binarne wymaga, aby elementy tablicy były porównywalne, co oznacza, że ​​musi istnieć możliwość ich uporządkowania.

Często zadawane pytania (FAQ) dotyczące wyszukiwania binarnego:

1. Co to jest wyszukiwanie binarne?

Wyszukiwanie binarne to skuteczny algorytm znajdowania wartości docelowej w posortowanej tablicy. Działa poprzez wielokrotne dzielenie interwału wyszukiwania na pół.

połączenie sql

2. Jak działa wyszukiwanie binarne?

Wyszukiwanie binarne porównuje wartość docelową ze środkowym elementem tablicy. Jeśli są równe, wyszukiwanie zakończyło się sukcesem. Jeśli cel jest mniejszy niż środkowy element, wyszukiwanie jest kontynuowane w dolnej połowie tablicy. Jeżeli cel jest większy, poszukiwania są kontynuowane w górnej połowie. Proces ten jest powtarzany do momentu znalezienia celu lub wyczerpania się interwału wyszukiwania.

3. Jaka jest złożoność czasowa wyszukiwania binarnego?

Złożoność czasowa wyszukiwania binarnego wynosi O (log2n), gdzie n jest liczbą elementów tablicy. Dzieje się tak, ponieważ w każdym kroku rozmiar interwału wyszukiwania jest zmniejszany o połowę.

4. Jakie są wymagania wstępne dotyczące wyszukiwania binarnego?

Wyszukiwanie binarne wymaga posortowania tablicy w kolejności rosnącej lub malejącej. Jeśli tablica nie jest posortowana, nie możemy użyć wyszukiwania binarnego do przeszukania elementu tablicy.

5. Co się stanie, jeśli tablica nie zostanie posortowana pod kątem wyszukiwania binarnego?

Jeśli tablica nie jest posortowana, wyszukiwanie binarne może zwrócić nieprawidłowe wyniki. Decyzja o tym, którą połowę tablicy należy przeszukać, opiera się na posortowanym charakterze tablicy.

6. Czy wyszukiwanie binarne można zastosować do danych nienumerycznych?

Tak, wyszukiwanie binarne można zastosować do danych nienumerycznych, o ile istnieje określona kolejność elementów. Można go na przykład wykorzystać do wyszukiwania ciągów znaków w kolejności alfabetycznej.

7. Jakie są typowe wady wyszukiwania binarnego?

Wadą wyszukiwania binarnego jest to, że tablica wejściowa musi zostać posortowana, aby zdecydować, w której połowie może znajdować się element docelowy. Dlatego w przypadku nieposortowanych tablic musimy je posortować przed zastosowaniem wyszukiwania binarnego.

8. Kiedy należy używać wyszukiwania binarnego?

Wyszukiwania binarnego należy używać podczas wyszukiwania wartości docelowej w posortowanej tablicy, zwłaszcza gdy rozmiar tablicy jest duży. Jest szczególnie skuteczny w przypadku dużych zbiorów danych w porównaniu z algorytmami wyszukiwania liniowego.

9. Czy wyszukiwanie binarne można zaimplementować rekurencyjnie?

Tak, wyszukiwanie binarne można wdrożyć zarówno iteracyjnie, jak i rekurencyjnie. Implementacja rekurencyjna często prowadzi do bardziej zwięzłego kodu, ale może wiązać się z nieco większym obciążeniem ze względu na rekurencyjną przestrzeń stosu lub wywołania funkcji.

10. Czy wyszukiwanie binarne jest zawsze najlepszym wyborem do wyszukiwania w posortowanej tablicy?

Chociaż wyszukiwanie binarne jest bardzo skuteczne w przypadku wyszukiwania w posortowanych tablicach, mogą wystąpić szczególne przypadki, w których bardziej odpowiednie będą inne algorytmy wyszukiwania, na przykład w przypadku małych zbiorów danych lub gdy tablica jest często modyfikowana.

Powiązane artykuły:

  • Wyszukiwanie binarne w samouczku odpowiedzi z problemami
  • Wyszukiwanie liniowe a wyszukiwanie binarne
  • Jak identyfikować i rozwiązywać problemy z wyszukiwaniem binarnym?