6 rodzajów algorytmów wyszukiwania i jak działają

Możesz wyobrazić sobie algorytmy wyszukiwania jako cyfrowych detektywów, odnajdujących to, czego potrzebujesz w ogromnych zbiorach danych, takich jak strony internetowe czy bazy danych, przy wykonaniu jak najmniejszej liczby kroków.

Od Google i Amazona po Facebooka i Netfliksa, algorytmy wyszukiwania odgrywają kluczową rolę w cyfrowych interakcjach w codziennym życiu.

W tym artykule dowiesz się o najpopularniejszych typach algorytmów wyszukiwania, ich złożoności czasowej, sposobie działania procesów wyszukiwania oraz ich rzeczywistych zastosowaniach w informatyce.

Niższa średnia złożoność przypadku przyspiesza wydajność, szczególnie w przypadku dużych wejść. Algorytmy takie jak wyszukiwanie binarne O(log n) są niezwykle wydajne.

Z drugiej strony, wyższe złożoności, takie jak O(n), mogą być niepraktyczne dla dużych zbiorów danych ze względu na wzrost liniowy, albo wzrost wyższy od niego. Wydajność zależy również od takich czynników jak kontekst problemu, źródła i wymagania aplikacji.

1. Algorytm wyszukiwania liniowego

Wyszukiwanie liniowe, znane również jako wyszukiwanie sekwencyjne, iteruje przez każdy element tablicy, porównując go z elementem docelowym, aż znajdzie dopasowanie. Jeśli funkcja wyszukiwania dotrze do końca tablicy bez znalezienia dopasowania, sygnalizuje, że element docelowy nie znajduje się w zbiorze danych.

Elementem docelowym mogą być liczby, ciągi znaków, obiekty lub dowolny inny typ danych, który może być przechowywany w tablicy. To szerokie spektrum możliwości powoduje, że wyszukiwanie liniowe jest wszechstronnym algorytmem, który może mieć zastosowanie w szerokim zakresie typu danych.

Aby lepiej zilustrować sam proces wyszukiwania, przeanalizujmy przykład.

Załóżmy, że posiadasz nieposortowaną listę liczb całkowitych reprezentujących wiek osób w grupie. Chcesz dowiedzieć się, czy określony wiek, powiedzmy 25 lat, jest obecny w tablicy. Prawdopodobnie zaczniesz od początku tablicy i po kolei sprawdzisz każdy element, aż znajdziesz wiek “25” lub dotrzesz do końca tablicy.

Czas wykonania algorytmu wyszukiwania liniowego jest proporcjonalny do rozmiaru tablicy. Złożoność obliczeniowa wyszukiwania liniowego wynosi O(n), gdzie n to liczba elementów w tablicy.

Zastosowanie wyszukiwania liniowego

• Proste zadania wyszukiwania: Wyszukiwanie liniowe często wykorzystuje się w szerokim spektrum podstawowych zadań wyszukiwania, w których zbiór danych jest niewielki lub dodatkowa złożoność innych algorytmów nie jest uzasadniona. Na przykład podczas przeszukiwania niewielkiej listy nazwisk lub liczb.
• Liniowe struktury danych: Wyszukiwanie liniowe ma fundamentalne znaczenie dla wielu liniowych struktur danych, takich jak tablice, listy i stosy. Zazwyczaj wykorzystuje się je do skanowania struktur w celu zlokalizowania określonych elementów lub wykonania danej operacji.
• Tablice nieuporządkowane: Ponieważ wyszukiwanie liniowe sprawdza każdy element sekwencyjnie, może zlokalizować elementy niezależnie od ich pozycji w tablicy.

2. Algorytm wyszukiwania binarnego

Wyszukiwanie binarne to wydajny algorytm wykorzystywany podczas wyszukiwania wartości docelowej na posortowanej liście. Wielokrotnie dzieli przedział wyszukiwania na pół, przy użyciu metody wyszukiwania binarnego. Następnie sprawdza wartość docelową względem środkowego elementu i przechodzi do prawej lub lewej części tablicy. Proces ten trwa do momentu znalezienia wartości docelowej. Interwał wyszukiwania może pozostać pusty, jeśli target nie znajduje się w tablicy.

Spójrzmy na przykładowe wykorzystanie wyszukiwania binarnego w znalezieniu określonej wartości liczbowej.

Wyobraź sobie tablicę liczb: [2,5,8,12,16,23,38,56,72,91] w której chcesz znaleźć liczbę 23.

Zacznijmy od spojrzenia na środkowy element (węzeł główny), którym jest liczba 16. Ponieważ liczba 23 jest większa niż 16, sprawdzamy tylko liczby na prawo od 16. Następnie przyjrzyjmy się środkowemu elementowi tej części, którym jest 56. Ponieważ liczba 23 jest mniejsza niż 56, sprawdzamy tylko liczby po lewej stronie liczby 56. Ponownie przyjrzyjmy się środkowemu elementowi, którym jest liczba 23. I tak klucz wyszukiwania został znaleziony.

Czas wykonania algorytmu wyszukiwania binarnego wynosi O (log n), gdzie n to liczba elementów w tablicy.

Zastosowania wyszukiwania binarnego

• Wyszukiwanie w bazach danych: Algorytm ten świetnie nadaje się do przeszukiwania baz danych w celu szybkiego lokalizowania rekordów na podstawie indeksowanych pól, takich jak identyfikatory lub klucze.
• Znajdowanie elementów w posortowanych tablicach: Wyszukiwanie binarne efektywnie lokalizuje elementy w posortowanych tablicach, co przydaje się w sytuacjach takich jak wyszukiwanie słowa w słowniku lub znajdowanie elementu na posortowanej liście.
• Podstawy algorytmiczne: To podstawowy element rozwoju zaawansowanych algorytmów uczenia maszynowego. Wyszukiwanie binarne pomaga w szkoleniu sieci neuronowych i optymalizacji hiperparametrów modelu.
• Optymalizacja algorytmów: Wyszukiwanie binarne wykorzystuje się w algorytmach, w tym w zasadach dziel i zwyciężaj, w celu skutecznego rozwiązywania problemów, takich jak znajdowanie pierwiastków kwadratowych lub lokalizowanie elementów szczytowych w tablicach.
• Wyszukiwanie w drzewach: Binarne drzewa poszukiwań (BST) wykorzystują  algorytm do wydajnego wyszukiwania, oraz wstawiania i usuwania elementów przy jednoczesnym zachowaniu posortowanej kolejności drzewa.

3. Wyszukiwanie interpolacyjne

Jeśli wartości w posortowanej tablicy są równomiernie rozłożone, wyszukiwanie interpolacyjne jest skuteczniejsze niż wyszukiwanie binarne. Interpolacja polega na tworzeniu nowych punktów danych w zakresie rozpoznanej przestrzeni wyszukiwania.

Podczas gdy wyszukiwanie binarne zawsze koncentruje się na środkowym elemencie, wyszukiwanie interpolacyjne dostosowuje swoją pozycję wyszukiwania w oparciu o szukaną wartość kluczową. Na przykład, jeśli klucz wyszukiwania znajduje się bliżej końca, wyszukiwanie interpolacyjne ma tendencję do rozpoczynania wyszukiwania od tego miejsca.

Aby lepiej zrozumieć zagadnienie, spróbuj sobie wyobrazić, że szukasz konkretnej ceny na wykazie asortymentu w sklepie. Ceny są ułożone od najniższej do najwyższej. Zamiast zaczynać od połowy listy (jak w przypadku wyszukiwania binarnego), wyszukiwanie interpolacyjne szacuje, gdzie cena może się znajdować. Robi to w oparciu o jej wartość w porównaniu do najniższej i najwyższej ceny. Następnie proces ten powtarza się aż do znalezienia ceny.

Czas wykonania algorytmu wyszukiwania interpolacyjnego wynosi O(log log n), gdzie n to liczba elementów w tablicy.

Zastosowania wyszukiwania interpolacyjnego

• Wyszukiwanie w bazach danych: Wyszukiwanie interpolacyjne  powszechnie stosuje się w bazach danych do znajdywania rekordów na podstawie danego elementu kluczowego.
• Wyszukiwanie w dużych tablicach: Ten rodzaj algorytmu wyszukiwania ułatwia wydajne wyszukiwanie w przypadku dużych, posortowanych tablic, zwłaszcza gdy rozkład wartości jest jednolity. Stosuje się go w różnych dziedzinach, takich jak obliczenia naukowe, gdzie duże zbiory danych muszą być przeszukiwane efektywnie.
• Odzyskiwanie danych z tablic symboli: Wyszukiwanie interpolacyjne można zastosować w tabelach symboli, w których klucze wiążą się z wartościami. Na przykład w językach programowania tabele symboli używa się do przechowywania zmiennych, funkcji oraz innych identyfikatorów. Wyszukiwanie interpolacyjne jest w stanie szybko zlokalizować informacje powiązane z określonym identyfikatorem.
• Aplikacje wrażliwe na czas: Ze względu na możliwość szybkiego pobierania danych, wyszukiwanie interpolacyjne świetnie nadaje się dla aplikacji uzależnionych od czasu.
• Tablice skrótów: wydajne narzędzie do wyszukiwania danych w połączeniu z funkcją skrótu.

4. Wyszukiwanie skokowe

Wyszukiwanie skokowe, inaczej zwane wyszukiwaniem blokowym, zostało stworzone z myślą o posortowanych tablicach. W przeciwieństwie do wyszukiwania liniowego, które sprawdza każdy element sekwencyjnie, wyszukiwanie skokowe przeskakuje przyrosty o stałym rozmiarze, omijając znaczną część elementów w celu szybszego wyszukiwania.

Jeśli element docelowy znajduje się w określonym przedziale, algorytm stosuje wyszukiwanie liniowe w ramach tego bloku. Takie podejście znacznie ogranicza liczbę operacji i wpływa na wydajność wyszukiwania.

Przyjrzyjmy się przykładowemu algorytmowi wyszukiwania skokowego.

Wyobraź sobie, że próbujesz znaleźć konkretną liczbę na długiej liście i chcesz poświęcić na to mniej czasu, niż na sprawdzanie każdej liczby z osobna.

1. Zdecyduj, ile liczb pominąć przy każdym wyszukiwaniu: Powiedzmy, że będziesz pomijać 3 liczby na raz.
2. Zacznij przeglądać listę, przeskakując za każdym razem wybraną wartość, aż znajdziesz liczbę równą lub większą od tej, której szukasz.
3. Po znalezieniu przedziału, w którym może znajdować się liczba, przejdź na wyszukiwanie liniowe, aż znajdziesz liczbę docelową.

Czas wykonania algorytmu wyszukiwania skokowego wynosi O(√n), gdzie n to liczba elementów w posortowanej tablicy.

Zastosowania wyszukiwania skokowego

• Aplikacje JavaScript: Wyszukiwanie skokowe optymalizuje proces wyszukiwania w aplikacjach JavaScript, wpływając na wydajność i szybkość reakcji.
• Wyszukiwanie w systemach baz danych: Algorytm wyszukuje rekordy na podstawie kluczowego elementu znajdującego się w dużych bazach danych.
• Pobieranie danych z mediów wizualnych: Wyszukiwanie skokowe skutecznie lokalizuje określoną klatkę w dużym pliku wideo, przesuwając stałą liczbę klatek na raz.

5. Wyszukiwanie wykładnicze

Algorytm wyszukiwania wykładniczego różni się od wyszukiwania skokowego sposobem podziału tablicy i rodzajem wyszukiwania zastosowanego w tych podziałach. Podczas gdy wyszukiwanie skokowe dzieli tablicę na bloki (przedziały) i wykorzystuje wyszukiwanie liniowe, wyszukiwanie wykładnicze dzieli tablicę przy użyciu wykładniczych potęg z 2 i stosuje wyszukiwanie binarne.

Funkcja wyszukiwania wykładniczego przechodzi przez całą tablicę od lewej strony, dzieląc ją na mniejsze bloki przy użyciu potęgi drugiej. Algorytm przeprowadza wyszukiwanie binarne w każdym z tych bloków, aż do znalezienia celu.

Ponieważ ten algorytm wyszukiwania może być nieco skomplikowany, spróbujmy zobrazować jego działanie.

Wyobraź sobie półkę pełną książek. Tytuły posortowano alfabetycznie. Szukasz konkretnej książki, powiedzmy “Harry Potter i Kamień Filozoficzny”. Zamiast przeszukiwać każdą książkę po kolei, decydujesz się użyć wyszukiwania wykładniczego.

Oto jak to działa:

1. Punkt wyjściowy: Zaczynasz od pierwszej książki od lewej. Jeśli nie jest to książka, której szukasz, przejdź dalej.
2. Przejdź w prawo, podwajając okno wyszukiwania: Jeśli znajdziesz “Harry’ego Pottera i Kamień Filozoficzny” w jednej z tych pozycji, brawo.
3. Powtórz proces: Powtórz proces, za każdym razem podwajając zakres, aż znajdziesz książkę.

Ten ogólny przykład pomaga zademonstrować, w jaki sposób można szybko zlokalizować książkę bez konieczności przeglądania każdej pozycji po kolei.

Czas wykonania algorytmu wyszukiwania wykładniczego wynosi O(log n), gdzie n to liczba elementów w posortowanej tablicy.

Zastosowania wyszukiwania wykładniczego

• Znajdowanie danych w obszernych posortowanych zbiorach: Wyszukiwanie wykładnicze szybko znajduje elementy w obszernych, posortowanych macierzach, takich jak zestawienia produktów, poprzez wykładnicze rozszerzanie zakresu wyszukiwania. To idealne rozwiązanie w sytuacjach, w których wyszukiwanie liniowe jest zbyt powolne.
• Przeszukiwanie systemów plików: Tego typu algorytm usprawnia wyszukiwanie w systemach plików, szybko znajdując pliki lub katalogi w strukturach katalogów, poprzez wykładnicze rozszerzenie zakresu wyszukiwania.

6. Wyszukiwanie ternarne

Wyszukiwanie ternarne to algorytm wyszukiwania przeznaczony do określania pozycji wartości docelowej w posortowanej tablicy. W przeciwieństwie do wyszukiwania binarnego, które dzieli tablicę na dwie części, wyszukiwanie ternarne dzieli ją na trzy. Za pomocą porównywania wartości docelowej z elementami w dwóch punktach i dzielenia tablicy na trzy części, funkcja wyszukiwania skutecznie zawęża przestrzeń wyszukiwania.

Poniżej znajduje się przykład zastosowania wyszukiwania ternarnego, które wykorzystamy do znalezienia liczby 6 w tablicy [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

• Podziel obszar wyszukiwania:
  • Podziel obszar wyszukiwania na trzy części, znajdując dwa punkty podziału: Jeden punkt znajduje się około jednej trzeciej drogi od lewej (powiedzmy 4), a drugi znajduje się około dwóch trzecich od lewej (powiedzmy 8).
  • To dzieli obszar na [1, 4], (5, 8) i [9, 10].
• Porównaj z targetem:
  • Sprawdź, czy szukana liczba (6) jest równa 4 lub 8.
  • Nie jest równa ani 4, ani 8, musisz dostosować wskaźniki w oparciu o to, gdzie może znajdować się 6:
    • Ponieważ 6 jest większe niż 4, ale mniejsze niż 8, przesuwamy lewy wskaźnik na 5, a prawy na 7.
• Powtórz lub zakończ:
  • Powtarzaj ten proces redukując przestrzeń wyszukiwania, aż znajdziesz liczbę 6 lub przeszukasz cały obszar.
  • Ostatecznie zawężysz obszar poszukiwań do [6, 6] i znajdziesz szukaną liczbę.

Czas wykonania algorytmu wyszukiwania ternarnego wynosi O(log3 n), gdzie n to liczba elementów w posortowanej tablicy.

Zastosowania wyszukiwania ternarnego

• Funkcje unimodalne: Wyszukiwanie ternarne stosuje się w funkcjach unimodalnych w celu określenia ich wartości maksymalnych lub minimalnych. Funkcje unimodalne to takie, które posiadają jedną najwyższą wartość.

Podsumowanie

Zastosowania różnych typów algorytmów wyszukiwania są ogromne i różnorodne, od przeszukiwania dużych baz danych i pomagania w optymalizacji aplikacji, po służenie jako podstawowe elementy składowe do tworzenia zaawansowanych algorytmów uczenia maszynowego do wyszukiwania.

Mając na uwadze złożoność czasową i pamięciową, możliwości, a także zalety i wady każdego z wymienionych algorytmów, możesz podejmować świadome decyzje. Niezależnie od tego, czy chodzi o zadanie na zajęciach z informatyki, czy o tworzenie kolejnej przełomowej aplikacji, opanowanie technik takich jak wyszukiwanie binarne, DFS, BFS oraz „dziel i rządź” pozwoli Ci uwolnić pełny potencjał struktur danych i zwiększyć wydajność systemu.

Jeśli tworzysz lub oceniasz wyszukiwarkę specjalnie dla sklepu internetowego, w praktyce jej mechanika działa nieco inaczej. Zobacz, jak działa wyszukiwanie w e-commerce od kulis.

Często zadawane pytania