Wyszukiwanie binarne

Wyszukiwanie binarne, to algorytm mający na celu sprawdzenie czy podany element znajduje się na posortowanej liście liczb oraz wskazanie jego miejsca. Działa w czasie logarytmicznym co nabiera znaczenia w przypadku dużych zbiorów danych.

Aby sprawdzić czy liczba L znajduje się w 1000 elementowej liście, przy zastosowaniu standardowej pętli typu For, w najgorszym przypadku potrzebujemy 1000 iteracji. Po prostu, musieli byśmy sprawdzać element po elemencie.

Z użyciem algorytmu wyszukiwania binarnego, 10.

Dla tablicy 1 000 000 elementów, pętla For potrzebuje w najgorszym przypadku 1 000 000 iteracji, algorytm wyszukiwania binarnego, 20.

Tak jak widzimy różnica jest olbrzymia. Jak ją osiągnąć?

Fundamenty działania algorytmu:

zbiór jest posortowany, w naszym przypadku, lista liczb
algorytm dzieli ją na dwie równe listy
sprawdza czy znalazł szukaną liczbę. Jeżeli nie, to sprawdza w który zbiór zawiera zakres liczb poszukiwanych. Czyli jeżeli widzi, że w zbiorze na lewo są liczby mniejsze, to nie zajmuje się szukaniem w tym zbiorze, tylko sprawdza zbiór
znowu, dzieli go na 2 równie zbiory
znowu sprawdza czy znalazł, znowu szukaną liczbę, dzieli zbiór itd.

Praktyczna porada:

Jest to kolejne zadanie, które jest o wiele łatwiejsze, jeżeli zanim zaczniemy programować, rozrysujemy je na kartce.

Przykładowe rozwiązanie.

def search (array, target): 
    
    # Definiujmey zmienne, przechowujące zakres, który badamy
    
    left = 0 
    right = len(array) 
    index = 0 
    
    # Sprawdzamy czy zakres który jest badany, nie jest pusty
    
    while left < right: 
        
        # dzielimy listę na 2 zbiory
        
        index = (left + right) // 2 
        
        # Jeżeli znaleźliśmy liczbę to kończymy
        # jeżeli lewa strona, jest mniejsza do ją odrzucamy
        # a jeżeli nie, to odrzucamy prawą stronę
        
        if array[index]==target_number: 
            return index 
        else: 
            if array[index]<target_number: 
                left = index+1 
            else: 
                right = index 
                
    return -1 

        
A = [1,3,4,5,7,9,11,15,16,17,19] 
target_number = 8 
index = search(A, target_number)

print (index)

Ćwiczenia Python, dla początkujących