Algorytm wyszukiwania binarnego

Algorytm wyszukiwania binarnego:

Algorytm wyszukiwania (binarnego) przez połowienie jest przykładem metody „dziel i zwyciężaj”.

Polega ona na dzieleniu przeszukiwanego zbioru na dwie części i zawężeniu przeszukiwania do jednej z tych części. Metoda podziału pomaga szybko znaleźć poszukiwany element, czyli zwyciężyć. W algorytmie wyszukiwania elementu w zbiorze uporządkowanym szukamy danego elementu i równocześnie jego położenia w tym zbiorze.

Przykładowa implementacje w Pythonie

a = [11, 23, 35, 44, 51, 59, 62, 71, 88, 91]
N = len(a)
 
def znajdz_dana(wartosc):
  poczatek = 0
  koniec = N - 1
  while poczatek <= koniec:
    srodek = (poczatek + koniec) // 2
    if a[srodek] == wartosc:
      return srodek
    else:
      if a[srodek] > wartosc:
          koniec = srodek - 1
      else:
          poczatek = srodek + 1
 
  return -1
 
szukana = 44 
pozycja = znajdz_dana(szukana)
if pozycja != -1:
    print(f'Liczbę {szukana} znaleziono na pozycji {pozycja}.')
else:
    print(f'W przeszukiwanej liście nie znaleziono liczby {szukana}.')