logo

TechCodeview

Algorytmy wyszukiwania

Algorytmy wyszukiwania to podstawowe narzędzia w informatyce używane do lokalizowania określonych elementów w zbiorze danych. Algorytmy te zostały zaprojektowane tak, aby efektywnie poruszać się po strukturach danych w celu znalezienia żądanych informacji, co czyni je podstawowymi w różnych zastosowaniach, takich jak bazy danych, wyszukiwarki internetowe , i więcej.

Algorytm wyszukiwania

Spis treści



Co to jest wyszukiwanie?

Poszukiwanie jest podstawowym procesem lokalizowanie określonego elementu lub elementu w zbiorze danych . Ten zbiór danych może przybierać różne formy, takie jak tablice, listy, drzewa lub inne ustrukturyzowane reprezentacje. Podstawowym celem wyszukiwania jest ustalenie, czy żądany element istnieje w danych, a jeśli tak, określenie jego dokładnej lokalizacji lub odzyskanie go. Odgrywa ważną rolę w różnych zadaniach obliczeniowych i zastosowaniach w świecie rzeczywistym, w tym w wyszukiwaniu informacji, analizie danych, procesach podejmowania decyzji i nie tylko.

Wyszukiwanie terminologii:

Element docelowy:

Podczas wyszukiwania zawsze istnieje określony element docelowy lub element, który chcesz znaleźć w zbiorze danych. Tym celem może być wartość, rekord, klucz lub dowolna inna jednostka danych.

Przeszukaj przestrzeń:

Przestrzeń poszukiwań odnosi się do całego zbioru danych, w obrębie którego szukasz elementu docelowego. W zależności od zastosowanej struktury danych przestrzeń wyszukiwania może różnić się wielkością i organizacją.

Złożoność:

Wyszukiwanie może mieć różny poziom złożoności w zależności od struktury danych i zastosowanego algorytmu. Złożoność często mierzy się wymaganiami czasowymi i przestrzennymi.

Deterministyczny a niedeterministyczny:

Niektóre algorytmy wyszukiwania, np wyszukiwanie binarne , są deterministyczne, co oznacza, że ​​stosują jasne, systematyczne podejście. Inne, takie jak wyszukiwanie liniowe, są niedeterministyczne, ponieważ w najgorszym przypadku mogą wymagać zbadania całej przestrzeni poszukiwań.

Znaczenie wyszukiwania w DSA:

  • Efektywność: Wydajne algorytmy wyszukiwania poprawiają wydajność programu.
  • Odzyskiwanie danych: Szybko znajduj i pobieraj określone dane z dużych zbiorów danych.
  • Systemy baz danych: Umożliwia szybkie odpytywanie baz danych.
  • Rozwiązywanie problemów: Stosowany w szerokim zakresie zadań związanych z rozwiązywaniem problemów.

Zastosowania wyszukiwania:

Algorytmy wyszukiwania mają wiele zastosowań w różnych dziedzinach. Oto kilka typowych zastosowań:

  • Wyszukiwanie informacji: Wyszukiwarki takie jak Google, Bing i Yahoo korzystają z zaawansowanych algorytmów wyszukiwania w celu wyszukiwania odpowiednich informacji z ogromnych ilości danych w Internecie.
  • Systemy baz danych: Wyszukiwanie ma fundamentalne znaczenie w systemach baz danych w celu wyszukiwania określonych rekordów danych na podstawie zapytań użytkowników, co poprawia efektywność wyszukiwania danych.
  • Handel elektroniczny: Wyszukiwanie ma kluczowe znaczenie na platformach handlu elektronicznego, ponieważ użytkownicy mogą szybko znajdować produkty na podstawie ich preferencji, specyfikacji lub słów kluczowych.
  • Sieć: W sieciach algorytmy wyszukiwania służą do wydajnego kierowania pakietów przez sieci, znajdowania optymalnych ścieżek i zarządzania zasobami sieciowymi.
  • Sztuczna inteligencja: Algorytmy wyszukiwania odgrywają kluczową rolę w zastosowaniach sztucznej inteligencji, takich jak rozwiązywanie problemów, granie w gry (np. W szachy) i procesy decyzyjne
  • Rozpoznawanie wzorców: Algorytmy wyszukiwania są używane w zadaniach dopasowywania wzorców, takich jak rozpoznawanie obrazu, rozpoznawanie mowy i rozpoznawanie pisma ręcznego.

Podstawy algorytmów wyszukiwania:

  • Wprowadzenie do wyszukiwania – samouczek dotyczący struktury danych i algorytmów
  • Znaczenie wyszukiwania w strukturze danych
  • Jaki jest cel algorytmu wyszukiwania?

Algorytmy wyszukiwania:

  • Wyszukiwanie liniowe
  • Wyszukiwanie liniowe Sentinel
  • Wyszukiwanie binarne
  • Wyszukiwanie metabinarne | Jednostronne wyszukiwanie binarne
  • Wyszukiwanie trójskładnikowe
  • Przeskocz wyszukiwanie
  • Wyszukiwanie interpolacyjne
  • Wyszukiwanie wykładnicze
  • Poszukiwanie Fibonacciego
  • Wszechobecne wyszukiwanie binarne

Porównania pomiędzy różnymi algorytmami wyszukiwania:

  • Wyszukiwanie liniowe a wyszukiwanie binarne
  • Wyszukiwanie interpolacyjne a wyszukiwanie binarne
  • Dlaczego wyszukiwanie binarne jest preferowane w stosunku do wyszukiwania trójskładnikowego?
  • Czy wyszukiwanie liniowe Sentinel jest lepsze niż zwykłe wyszukiwanie liniowe?

Bibliotekowe implementacje algorytmów przeszukiwania:

  • Funkcje wyszukiwania binarnego w C++ STL (wyszukiwanie_binarne, dolna granica i górna granica)
  • Arrays.binarySearch() w Javie z przykładami | Zestaw 1
  • Arrays.binarySearch() w Javie z przykładami | Zestaw 2 (Szukaj w podtablicy)
  • Collections.binarySearch() w Javie z przykładami

Łatwe problemy z wyszukiwaniem:

  • Znajdź trzy największe elementy w tablicy
  • Znajdź brakujący numer
  • Znajdź pierwszy powtarzający się element w tablicy liczb całkowitych
  • Znajdź brakujący i powtarzający się numer
  • Wyszukaj, wstaw i usuń w posortowanej tablicy
  • Policz 1 w posortowanej tablicy binarnej
  • Dwa elementy, których suma jest najbliższa zeru
  • Znajdź parę o podanej różnicy
  • k największych (lub najmniejszych) elementów tablicy
  • K-ty najmniejszy element tablicy 2D posortowanej wierszowo i kolumnowo
  • Znajdź wspólne elementy w trzech posortowanych tablicach
  • Sufit w posortowanym szyku
  • Podłoga w posortowanej tablicy
  • Znajdź maksymalny element w tablicy, który najpierw rośnie, a następnie maleje
  • Mając tablicę o rozmiarze n i liczbie k, znajdź wszystkie elementy, które pojawiają się więcej niż n/k razy

Średnie problemy z wyszukiwaniem:

  • Znajdź wszystkie trójki z sumą zerową
  • Znajdź element, przed którym wszystkie elementy są od niego mniejsze, a po którym wszystkie są większe
  • Znajdź największą sumę par w nieposortowanej tablicy
  • K’th najmniejszy/największy element w nieposortowanej tablicy
  • Wyszukaj element w posortowanej i obróconej tablicy
  • Znajdź minimalny element w posortowanej i obróconej tablicy
  • Znajdź element szczytowy
  • Maksimum i minimum tablicy przy użyciu minimalnej liczby porównań
  • Znajdź punkt stały w danej tablicy
  • Znajdź k najczęściej występujących słów z pliku
  • Znajdź k elementów najbliższych danej wartości
  • Biorąc pod uwagę posortowaną tablicę i liczbę x, znajdź parę w tablicy, której suma jest najbliższa x
  • Znajdź najbliższą parę z dwóch posortowanych tablic
  • Znajdź trzy najbliższe elementy z podanych trzech posortowanych tablic
  • Binarne wyszukiwanie liczb wymiernych bez użycia arytmetyki zmiennoprzecinkowej

Trudne problemy z wyszukiwaniem:

  • Mediana dwóch posortowanych tablic
  • Mediana dwóch posortowanych tablic o różnych rozmiarach
  • Szukaj w prawie posortowanej tablicy
  • Znajdź pozycję elementu w posortowanej tablicy nieskończonych liczb
  • Mając posortowaną i obróconą tablicę, sprawdź, czy istnieje para o podanej sumie
  • K’th najmniejszy/największy element w nieposortowanej tablicy | W najgorszym przypadku czas liniowy
  • K’ – największy element strumienia
  • Najlepsze pierwsze wyszukiwanie (świadome wyszukiwanie)

Szybkie linki:

  • „Zadania praktyczne” dotyczące wyszukiwania
  • „Quizy” dotyczące wyszukiwania

Zalecana:

  • Naucz się struktury danych i algorytmów | Poradnik DSA