Co to jest wyszukiwanie binarne?

Wyszukiwanie binarne to algorytm wyszukiwania używany do wyszukiwania elementów docelowych w pojemniku, w którym elementy muszą być ułożone w kolejności rosnącej. Zasadniczo wyszukiwanie binarnych jest używane do wyszukiwania numeru indeksu elementu docelowego w posortowanej tablicy.

Wyszukiwanie binarne wykorzystuje podejście podziału i podbijania, w którym dzieli tablicę na równe części, aż znajdzie element docelowy.

Algorytm wyszukiwania binarnego jest wdrażany zarówno iteracyjny, jak i rekurencyjny. Wyszukiwanie binarne jest bardziej wydajne i szybsze w porównaniu z wyszukiwaniem liniowym.

Algorytm wyszukiwania binarnego

1. Sortuj i ułóż elementy w tablicy arr w kolejności rosnącej.
2. Algorytmy porównują element środkowy N z elementem docelowym cel.
3. Algorytm zwraca wskaźnik pozycji elementu środkowego, jeśli element docelowy jest równy elementowi środkowego,
4. Algorytm przeszukuje dolną połowę tablicy, jeśli element docelowy jest mniejszy niż element środkowy.
5. Algorytm przeszukuje górną połowę tablicy, jeśli element docelowy jest większy niż element środkowy.
6. Algorytm powtarza 4. i 5. kroki, aż długość tablicy stanie się jednym lub mniej niż 1.

Do końca albo wartość indeksu elementu jest zwracana, albo element nie istnieje w tablicy.

Pseudocode wyszukiwania binarnego

Wielokrotny

funkcja binary_search (arr, n, cel) jest
po lewej: = 0
po prawej: = n - 1
podczas gdy lewe ≤ prawy
Środek: = podłoga ((po lewej + prawej) / 2)
Jeśli ARR [środkowy] cel, to
po prawej: = środkowy - 1
w przeciwnym razie:
powrót środka
powrót nieudany

Rekurencyjny

funkcja binary_search (ARR, lewy, prawy, cel) jest
Jeśli po prawej> = lewy
Middle = (lewy+prawy) // 2
Jeśli ARR [Middle] == cel
powrót środka
W przeciwnym razie, jeśli arr [środkowy]> target
return binary_search (ARR, niski, połowa 1, cel)
w przeciwnym razie
return binary_search (ARR, MID+1, po prawej, cel)
w przeciwnym razie
powrót nieudany

Wdrożyć wyszukiwanie binarne w Python

Wielokrotny
W podejściu iteracyjnym używamy pętli do wdrożenia wyszukiwania binarnego.

def binary_search (arr, n, cel):
po lewej = 0
Right = n-1
Middle = 0
w lewo<=right:
Middle = (prawy+lewy) // 2
#Jeśli element środkowy jest równy elementowi docelowi
Jeśli ARR [Middle] == cel:
powrót środka
# Jeśli element docelowy jest większy niż element środkowy
Elif Arr [Middle]< target:
po lewej = środkowy+1
# Jeśli element docelowy jest mniejszy niż element środkowy
w przeciwnym razie:
Right = Middle-1
# Jeśli element docelowy nie jest obecny w tablicy
zwrot -1
Jeśli __name__ == '__main__':
# posortowana tablica
sorted_arr = [0,4,7,10,14,23,45,47,53]
# długość tablicy
n = len (sorted_arr)
#Element do wyszukiwania
Target = 47
pozycja = binary_search (sorted_arr, n, cel)
Jeśli pozycja != -1:
print (f "element targ obecny w indeksowaniu pozycja")
w przeciwnym razie:
print (f "element targ nie występuje w tablicy")

Wyjście

Element 47 obecny na indeksie 7

Rekurencyjny
W Recursive zamiast używania pętli, ciągle wywołujemy funkcję, aż stan podstawowy nie zostanie zadowolony

def binary_search (ARR, lewy, prawy, cel):
#base warunek
Jeśli RightTarget:
return binary_search (ARR, po lewej, środkowej 1, cel)
#if Element docelowy jest mniejszy niż element środkowy
w przeciwnym razie:
return binary_search (ARR, Middle+1, po prawej, cel)
Jeśli __name__ == '__main__':
# posortowana tablica
sorted_arr = [0,4,7,10,14,23,45,47,53]
po lewej = 0
right = len (sorted_arr) -1
#Element do wyszukiwania
Target = 47
pozycja = binary_search (sorted_arr, lewy, prawy, cel)
Jeśli pozycja != -1:
print (f "element targ obecny w indeksowaniu pozycja")
w przeciwnym razie:
print (f "element targ nie występuje w tablicy")

Wyjście

Element 90 nie jest obecny w tablicy

Złożoność

Wyszukiwanie binarne ma złożoność czasu O (log n), gdzie N to liczba elementów obecnych w tablicy.

Wyszukiwanie binarne ma złożoność przestrzeni O (1), ponieważ w algorytmie wykonujemy wyszukiwanie na miejscu.

Wniosek

Wyszukiwanie binarne jest jednym z najlepszych i wydajnych algorytmów wyszukiwania. Złożoność czasu i przestrzeni wyszukiwania binarnego jest również bardzo niska; Jedynym warunkiem wyszukiwania binarnego jest to, że tablica wejściowa powinna być sortowana w kolejności rosnącej.