Czym jest wyszukiwanie liniowe?
Wyszukiwanie liniowe to prosty algorytm sprawdzający kolejno elementy kolekcji, np. tablicy, aż do znalezienia szukanej wartości albo dojścia do końca kolekcji.
Algorytm nie wymaga, aby dane były posortowane. Działa poprawnie zarówno dla tablic uporządkowanych, jak i nieuporządkowanych.
Zasada działania
Dla każdego elementu tablicy:
- porównaj element z szukaną wartością,
- jeśli są równe, zakończ działanie i zwróć informację o znalezieniu,
- jeśli pętla zakończy się bez znalezienia elementu, zwróć informację, że elementu nie ma.
Przykład w C++
bool czyJest(int argument)
{
int T[] = {4, 15, -2, 9, 202};
for (int i = 0; i < 5; i++) {
if (T[i] == argument)
return true;
}
return false;
}
Funkcja zwróci true, jeśli argument znajduje się w tablicy, np. dla wartości 9. Zwróci false, jeśli wartości nie ma, np. dla 100.
Złożoność obliczeniowa
- najlepszy przypadek:
O(1)— element jest na początku tablicy, - najgorszy przypadek:
O(n)— element jest na końcu albo nie występuje, - średni przypadek:
O(n).
Kiedy stosować?
Wyszukiwanie liniowe sprawdza się przy małych tablicach lub wtedy, gdy dane nie są posortowane. Przy dużych, posortowanych zbiorach zwykle lepsze jest wyszukiwanie binarne.