Wyszukanie konkretnego fragmentu informacji w wielkich zbiorach uprzednio zapamiętanych danych jest operacją podstawową, nazywaną wyszukiwaniem, będącą nieodłączną częścią wielu prac komputerowych [Sedgewick]. Dane są podzielone na elementy (rekordy), z których każdy zawiera klucz wykorzystywany przy wyszukiwaniu.
Zbiór danych może być w pewnych przypadkach nieuporządkowany, a w innych przypadkach całkowicie uporządkowany (posortowany). Często wykorzystuje się częściowe uporządkowanie zbioru w pewnych strukturach danych (drzewa binarne, kopce), aby przyspieszyć operację wyszukiwania. Ważnym czynnikiem występującym w zastosowaniach jest zmienność zawartości zbioru z danymi (elementy są dodawane lub usuwane ze zbioru). Dlatego interesują nas dynamiczne struktury danych, zmieniające się w czasie pracy. Chcemy, aby operacje na zbiorze danych wykonywały się możliwie szybko. Wybór optymalnej struktury danych zależy od spodziewanego wzorca działań na zbiorze (czy występują częste modyfikacje zbioru, czy często powtarzają się zapytania z takimi samymi kluczami, itp.).
Tablica asocjacyjna (słownik) jest to ADT przechowujący pary (klucz, wartość) i umożliwiający trzy podstawowe działania: wstawienie nowej pary, wyszukanie wartości związanej z podanym kluczem, usunięcie pary związanej z danym kluczem.
Inny rodzaj wyszukiwania opisują statystyki pozycyjne.
W zbiorze n-elementowym i-ty najmniejszy element nazywamy i-tą statystyką pozycyjną [Cormen str. 210]. Minimum zbioru jest jego pierwszą statystyką pozycyjną (i=1). Maksimum zbioru jest jego n-tą statystyką pozycyjną.
Wiele algorytmów wyszukiwania opiera się na drzewie poszukiwań binarnych, które chcemy utrzymywać w stanie zrównoważenia.
Problem selekcji (wyboru) to problem wyznaczania k-tej co do wielkości wśród n liczb.
SPECYFIKACJA Problem wyboru. DANE WEJŚCIOWE Zbiór A (parami różnych) n liczb oraz liczba k taka, że 1 <= k <= n. DANE WYJŚCIOWE Element zbioru A większy od dokładnie k-1 innych elementów zbioru A.
Dla niektórych wartości k (1 lub n) problem jest bardzo prosty i wymaga jedynie wyznaczenia minimalnej lub maksymalnej wartości w A, co możemy zrobić w czasie O(n). Bardziej skomplikowanym problemem jest znajdowanie mediany (k=n//2). Szybkie znajdowanie mediany pozwoliłoby np. poprawić algorytm sortowania quicksort tak, aby nawet w pesymistycznym przypadku działał w czasie O(n log n).
Wybrane algorytmy wyszukiwania.