wyszkukiwanie

Problem wyszukiwania w programowaniu – cz. 1 (wyszukiwanie binarne)

Problem wyszukiwania w programowaniu jest jednym z najważniejszych problemów algorytmicznych. Można nie tylko przeszukiwać zbiory liczb, czy innych obiektów, ale także szukać optymalnego wyniku.

Wyszukiwanie liniowe – O(n)

 

Najprostszym i najbardziej trywialnym rozwiązaniem jest algorytm wyszukiwania liniowego, który jak sama nazwa wskazuje działa w czasie O(n).

Przykładowa implementacja:

 

 

Powyższy kod sprawdza każdą liczbę ze zbioru i jeśli jest natrafi na szukaną wartość zwraca jej indeks(gdy w tablicy jest więcej takich samych liczb, to funkcja zwróci indeks pierwszej), gdy takowej nie ma to funkcji zwróci -1.

Bardzo łatwo można przekształcić powyższe rozwiązanie, tak by zwracało indeks ostatniego wystąpienie szukanego elementu.

 

To rozwiązanie staje się jednak nieefektywne, gdy szukamy np. wiele liczb w tablicy. Natchnienia do wymyślenia czegoś szybszego musimy szukać w codziennym życiu 😉


 

W poszukiwaniu lepszego rozwiązania

Skoro potrzebujemy szybszego algorytmu szukającego, przyjrzyjmy się jak sobie z tym radzimy na co dzień.  Zadajmy sobie pytanie:

 

Jak poszukujemy frazy w słowniku?

Czy robimy to tak jak w naszym poprzednim algorytmie?

 

Odpowiedź jest oczywista: NIE!

Przecież nikt nie będzie sprawdzał każdego jednego słówka w słowniku. To potrwało by wieki. Korzystamy z fajnej własności słownika. Słownik jest przecież posortowany alfabetycznie. Przez to wiemy, że jak szukamy czegoś na literę ‘R’, a słownik mamy otworzony na literze ‘L’, to wiemy, że wszystkie poprzednie strony można już odrzucić, bo wiadomo, że szukanego wyrazu tam nie będzie. W taki sposób coraz bardziej zawężamy pole przeszukiwania i po kilku sprawdzeniach mamy wynik, pomimo że wyrazów jest ponad 100 tysięcy!

Jak zatem przenieść naszą znakomitą metodę szukania do funkcji?


 

Wyszukiwanie “z życia wzięte” binarne – O(log n)

 

Jeszcze przed tworzeniem jakichkolwiek implementacji należałoby upewnić się czy nasze rozwiązanie jest rzeczywiście takie idealne. Musimy bowiem pamiętać, że zadziało ono tylko w przypadku, gdy nasz tablica jest posortowana, inaczej nigdy nie możemy założyć, że naszego elementu na pewno nie będzie w jakimś przedziale. Na nasze szczęście znane są algorytmy sortowanie w czasie O(n log n), więc niewiele gorszym od liniowego, a przecież sortować będziemy tylko raz. O tych algorytmach powstaną posty w przyszłości, dziś mogę polecić tylko funkcję sort z C++ lub (lepiej) zagłębienie się w temat i poszukanie materiałów na własną rękę.

 

Skoro założenia mamy za sobą przejdźmy do meritum.

 

Przejdźmy zatem do pierwszego kroku naszego algorytmu, czyli:

 

Jak wybrać element do sprawdzenia, tak by odrzucić jak najwięcej rzeczy?

 

Odpowiedź to oczywiście podzielić na 2 równe części. Jeśli wybierzemy jakikolwiek inny element podziału niż środek zawsze istnieje szansa(50%), że szukany element będzie w tej większej części.

Następny krok to sprawdzenie zgodności elementu i wybranie przedziału, co już trudne nie jest.

  • Równa się – znaleźliśmy szukaną wartość;
  • Za duża – szukać powinniśmy wśród mniejszych liczb
  • Za mała – szukać musimy wśród większych liczb

 

Teraz zostało nam tylko to zaimplementować:

 

 

Powyższy kod realizuje nasz pomysł, który nosi nazwę wyszukiwanie binarne. Prawdopodobnie nazwa wzięła się z tego, że podstawą szukania jest dzielenia przez 2. Złożoność tego algorytmu to O(log n), więc dla wyszukania liczby w tablicy mającej milion elementów potrzeba zaledwie 20 sprawdzeń, nawet gdy danej liczby nie ma w naszej tablicy. Jest to zatem ogromne przyspieszenie, dzięki któremu można rozwiązywać wiele problemów.

Technika zastosowana przy tworzeniu tego rozwiązania również ma własną nazwę: “Dziel i zwyciężaj“. Jej zastosowanie jest bardzo szerokie i warto o niej pamiętać. Polega ona na dzieleniu problemu na mniejsze, co ma pozwolić zmniejszyć czas działania programu.


Podsumowanie

Zachęcam każdego czytelnika do zapoznania się z ćwiczeniami dostępnymi tutaj. W części 2 będę omawiał rozwiązania do nich i tym samym praktyczne zastosowania wyszukiwania binarnego. Zachęcam do zadawania pytań i pisania wszelakich uwag w sekcji komentarzy. Mam nadzieję, że wpis się podobał i że wszystko było zrozumiałe 😉

5 thoughts on “Problem wyszukiwania w programowaniu – cz. 1 (wyszukiwanie binarne)

  1. Zdaję sobie sprawę, że pokazujesz algorytm i użycie gotowca tutaj koliduje z przesłaniem, ale mimo wszystko warto wspomnieć o istnieniu std::find, std::find_if i std::binary_search, aby, już po zrozumieniu zagadnienia, czytelnicy wiedzieli, że nie muszą wymyślać koła na nowo 🙂

    1. Optymalne algorytmy sortowania są bardziej złożone od samego wyszukiwania, więc poruszę ten temat za kilka postów. Gotowce do danego tematu wraz z przykładami “jak używać” będą zawsze na samym końcu(w tym przypadku w ostatniej części). Sam system bin-search’u zawsze warto znać. Szersze zastosowanie będzie w cz. 2 wraz z omawianiem ćwiczeń(np. przy technice wyszukiwania po wyniku częściej pisze się własną implementacje). Prócz twoich wymienionych gotowców będzie o lower_bound(nie mniejszy niż) i upper_bound(pierwszy większy) 🙂

  2. Hej, fajny post – mógłbyś dopisać dlaczego lepiej jest posortować zbiór, jeśli mamy dużo wyszukań, ja widzę że w podtekście jest tutaj że nlog(n) mniejsze od n^2, ale nie jest to explicite napisane.

    Masz też w snippetach złe kodowanie >, <, itp: int szukaj(int x, vector<int> &v)

    Pozdrawiam 🙂 i czekam na kolejne posty.

    1. Dzięki za zwrócenie uwagi. Już poprawiłem to, jak i kilka innych literówek.

      Masz rację, że powinienem był dopisać coś o sumarycznej złożoności. Prócz tego chcę opisać samą notację ‘O’. Ogólnie jest nad czym pracować.

      Również pozdrawiam 😉

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *