Wyszukiwanie liniowe
Ostatnia aktualizacja
Wyszukiwanie liniowe (nazywane też sekwencyjnym) to najprostszy algorytm wyszukiwania: zaczynasz od pierwszego elementu i porównujesz każdy kolejny z celem, aż znajdziesz dopasowanie albo skończą się elementy. Algorytm nie zakłada niczego o danych, więc tablica może być nieposortowana, a elementami może być wszystko, co da się porównać pod kątem równości.
Animacja powyżej podświetla każde porównanie, gdy przeglądanie przesuwa się od lewej do prawej, i zatrzymuje się w chwili, gdy pojawi się cel. Prostota kosztuje szybkość: w najgorszym przypadku sprawdzany jest każdy element, więc algorytm działa w O(n). Gdy dane są posortowane, wyszukiwanie binarne znajduje tę samą odpowiedź w O(log n), a jeśli najpierw potrzebujesz posortować dane, zobacz merge sort.
Złożoność czasowa i pamięciowa
| Przypadek | Złożoność | Uwagi |
|---|---|---|
| Najlepszy przypadek | O(1) | Pierwszy element jest celem. |
| Średni przypadek | O(n) | Średnio połowa elementów jest sprawdzana przed trafieniem. |
| Najgorszy przypadek | O(n) | Cel jest ostatni albo w ogóle go nie ma. |
| Pamięć | O(1) | Przechowywany jest tylko bieżący indeks. |
Krok po kroku
| Krok | Co się dzieje |
|---|---|
| 1 | Zacznij od indeksu 0, czyli pierwszego elementu tablicy. |
| 2 | Porównaj bieżący element z szukaną wartością. |
| 3 | Jeśli są równe, zwróć bieżący indeks (znaleziono). |
| 4 | W przeciwnym razie przesuń się o jedną pozycję w prawo i powtórz. |
| 5 | Jeśli dojdziesz do końca tablicy bez dopasowania, celu nie ma (zwróć -1). |
Przykład krok po kroku
Szukanie 5 w [7, 3, 9, 1, 5, 8, 2]:
| Porównanie | Indeks | Element | Wynik |
|---|---|---|---|
| 1 | 0 | 7 | 7 ≠ 5: przeglądaj dalej. |
| 2 | 1 | 3 | 3 ≠ 5: przeglądaj dalej. |
| 3 | 2 | 9 | 9 ≠ 5: przeglądaj dalej. |
| 4 | 3 | 1 | 1 ≠ 5: przeglądaj dalej. |
| 5 | 4 | 5 | 5 = 5: znaleziono pod indeksem 4. |
Kiedy używać wyszukiwania liniowego
| Używaj, gdy | Unikaj, gdy |
|---|---|
| Dane są nieposortowane lub ciągle się zmieniają | Dane są posortowane, więc wyszukiwanie binarne jest wykładniczo szybsze |
| Kolekcja jest mała, więc wygrywa prostota | Zbiór danych jest duży i przeszukiwany wielokrotnie |
| Masz tylko dostęp sekwencyjny (strumienie, listy jednokierunkowe) | Stać cię na indeks lub tablicę haszującą z wyszukiwaniem w O(1) |
Linear Search: kod
Przejrzysta, gotowa do uruchomienia implementacja algorytmu Linear Search w językach: Python, JavaScript, Java, C++, C, Pseudocode. Wybierz język, skopiuj kod albo otwórz go od razu w edytorze online Coddy.
Linear Search: kod (Python)
Python
1def linear_search(a, target):2 # Scan left to right until the target appears3 for i in range(len(a)):4 if a[i] == target:5 return i6 return -17
8
9nums = [7, 3, 9, 1, 5, 8, 2]10print("Index of 5:", linear_search(nums, 5))11print("Index of 4:", linear_search(nums, 4))Linear Search: kod (JavaScript)
JavaScript
1function linearSearch(a, target) {2 // Scan left to right until the target appears3 for (let i = 0; i < a.length; i++) {4 if (a[i] === target) return i;5 }6 return -1;7}8
9const nums = [7, 3, 9, 1, 5, 8, 2];10console.log("Index of 5:", linearSearch(nums, 5));11console.log("Index of 4:", linearSearch(nums, 4));Linear Search: kod (Java)
Java
1public class Main {2 static int linearSearch(int[] a, int target) {3 // Scan left to right until the target appears4 for (int i = 0; i < a.length; i++) {5 if (a[i] == target) return i;6 }7 return -1;8 }9
10 public static void main(String[] args) {11 int[] nums = {7, 3, 9, 1, 5, 8, 2};12 System.out.println("Index of 5: " + linearSearch(nums, 5));13 System.out.println("Index of 4: " + linearSearch(nums, 4));14 }15}Linear Search: kod (C++)
C++
1#include <iostream>2#include <vector>3
4int linearSearch(const std::vector<int>& a, int target) {5 // Scan left to right until the target appears6 for (std::size_t i = 0; i < a.size(); i++) {7 if (a[i] == target) return static_cast<int>(i);8 }9 return -1;10}11
12int main() {13 std::vector<int> nums = {7, 3, 9, 1, 5, 8, 2};14 std::cout << "Index of 5: " << linearSearch(nums, 5) << "\n";15 std::cout << "Index of 4: " << linearSearch(nums, 4) << "\n";16 return 0;17}Linear Search: kod (C)
C
1#include <stdio.h>2
3int linear_search(const int a[], int n, int target) {4 /* Scan left to right until the target appears */5 for (int i = 0; i < n; i++) {6 if (a[i] == target) return i;7 }8 return -1;9}10
11int main(void) {12 int nums[] = {7, 3, 9, 1, 5, 8, 2};13 int n = sizeof(nums) / sizeof(nums[0]);14 printf("Index of 5: %d\n", linear_search(nums, n, 5));15 printf("Index of 4: %d\n", linear_search(nums, n, 4));16 return 0;17}Linear Search: kod (Pseudocode)
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74nums[1] ← 75nums[2] ← 36nums[3] ← 97nums[4] ← 18nums[5] ← 59nums[6] ← 810nums[7] ← 211
12FUNCTION linearSearch(target : INTEGER) RETURNS INTEGER13 DECLARE i : INTEGER14 // Scan left to right until the target appears15 FOR i ← 1 TO n16 IF nums[i] = target THEN17 RETURN i18 ENDIF19 NEXT i20 RETURN -121ENDFUNCTION22
23OUTPUT "Index of 5 is ", linearSearch(5)24OUTPUT "Index of 4 is ", linearSearch(4)Wyszukiwanie liniowe: najczęstsze pytania
Jaka jest złożoność czasowa wyszukiwania liniowego?
O(n) w średnim i najgorszym przypadku (przeglądanie może wymagać odwiedzenia każdego elementu) oraz O(1) w najlepszym przypadku, gdy pierwszy element jest celem. Zużywa O(1) dodatkowej pamięci.Czy wyszukiwanie liniowe wymaga posortowanych danych?
Nie, i to jego główna zaleta. Wyszukiwanie liniowe działa na całkowicie nieposortowanych danych, bo sprawdza równość każdego elementu; kolejność nigdy nie ma znaczenia. Wyszukiwanie binarne działa natomiast tylko na posortowanych tablicach.
Kiedy wyszukiwanie liniowe jest lepsze od binarnego?
Gdy dane są nieposortowane i przeszukujesz je tylko raz (wcześniejsze sortowanie kosztowałoby
O(n log n)), gdy kolekcja jest malutka albo gdy masz tylko dostęp sekwencyjny, na przykład strumień lub listę jednokierunkową. Przy wielokrotnych wyszukiwaniach w posortowanych tablicach wygrywa wyszukiwanie binarne.Czy wyszukiwanie liniowe to to samo co wyszukiwanie sekwencyjne?
Tak, obie nazwy opisują ten sam algorytm: przeglądaj elementy po kolei, aż znajdziesz cel albo skończy się kolekcja.
Ile porównań średnio wykonuje wyszukiwanie liniowe?
Jeśli cel istnieje i z równym prawdopodobieństwem może być wszędzie, średnio około
n/2 porównań; jeśli celu nie ma, dokładnie n. Ten liniowy wzrost jest powodem nazwy wyszukiwanie liniowe.Powiązane materiały
Więcej wizualizacji
