Wyszukiwanie liniowe i binarne [Python] odc. 16 z serii podstaw Pythona

W tym odcinku omawiam dwa podstawowe algorytmy wyszukiwania elementów w liście, to jest algorytmy wyszukiwania liniowego oraz binarnego.
Wyszukiwanie liniowe polega na przejściu przez całą listę i porównywaniu po kolei każdego elementu z szukanym kluczem. Jeśli wartość stojąca na danej pozycji w liście równa jest szukanej wartości, zwracamy indeks danego elementu. Jeśli szukana wartość stoi na pierwszym miejscu w liście to wszystko spoko, wystarczy jedna operacja do znalezienia szukanego indeksu. Co, jeśli jednak szukanej wartości wcale nie ma w naszej liście? Dowiemy się o tym dopiero po przejściu przez całą listę. Dla listy n-elementowej będziemy musieli wykonać n operacji. Złożoność czasowa tego algorytmu to O(n).
Zdecydowanie szybszym algorytmem jest algorytm wyszukiwania binarnego. Algorytm ten opiera się na strategii, dziel i zwyciężaj. W pierwszym kroku sprawdzamy, czy element siedzący pośrodku listy, równa się szukanej wartości. Jeśli tak, gotowe. W przeciwnym razie sprawdzamy, czy jest od niej mniejszy, czy większy. Jeśli szukana wartość jest mniejsza od środkowego elementu, to znajduje się gdzieś na pozycjach mniejszych od tego elementu. Jeśli jest większe, to siedzi gdzieś na pozycjach większych od środkowego elementu. W następnym kroku powtarzamy całą operację. Wyszukiwanie binarne w każdym kroku odrzuca połowę aktualnie rozpatrywanych elementów listy. Wyszukiwanie binarne jest algorytmem logarytmicznym o złożoności O(logn).
Dla listy posiadającej milion elementów wyszukiwanie binarne w najgorszym wypadku będzie wymagało od nas miliona (1 000 000) operacji, natomiast wyszukiwanie binarne ledwo 20 :)
Jedyną wadą algorytmu wyszukiwania binarnego jest fakt, że działa on jedynie dla list posortowanych!
Kod:
github.com/dje...

[@MrBenios]

Fajny filmik, wszystko ładnie wytłumaczone :3

[@bartdziubek327]

dobry odcinek stworzyłeś, materiały w praktyce są dużo lepsze niż "suche" pokazywanie co dana czynność wykonuje :)

[@morf01]

Witam, bardzo fajny film który jasno tłumaczy zagadnienie, ale wydaje mi się że jest błąd w funkcji wyszukiwanie_binarne(). Zmienna r = len(lista) - 1, bez tego mamy otryzmamy IndexError jeśli szukamy liczby większej od wszystkich liczb na liście

[@szymon0777]

To samo zauważyłem właśnie

[@wojciechsuchecki5690]

Super odcinek :)
Ale dlaczego lista już na początku jest posortowana ?

[@AdamDjellouli]

Wyszukiwanie binarne działa tylko dla zbiorów uporządkowanych.