Wyszukiwanie liniowe: Python, C++ Przykład

Czym jest algorytm wyszukiwania?

Algorytm wyszukiwania jest zaprojektowany w celu znalezienia elementu lub obiektu ze zbioru elementów lub obiektów o danej strukturze danych. Na przykład wyszukaj minimalną wysokość z danej listy wysokości lub wyszukaj najwyższy znak z listy lub tablicy liczb. Kilka popularnych algorytmów wyszukiwania obejmuje „wyszukiwanie liniowe”, „wyszukiwanie binarne”, „wyszukiwanie skokowe”, „wyszukiwanie Fibonacciego” itp.

Co to jest wyszukiwanie liniowe?

Przeszukiwanie liniowe jest jednym z najprostszych algorytmów wyszukiwania. Z podanej listy lub tablicy wyszukuje on po kolei dany element. Przeszukiwanie liniowe iteruje po całej liście i sprawdza, czy którykolwiek konkretny element jest równy elementowi wyszukiwania. Jest ono również nazywane wyszukiwanie sekwencyjne.

Do czego służy funkcja wyszukiwania liniowego?

Tablicę liczb całkowitych podaje się jako „Numbers”, a zmienna „item” zawiera liczbę całkowitą do przeszukania.

Teraz algorytm wyszukiwania liniowego może dostarczyć następujący wynik:

„-1”; oznacza to, że danego elementu nie znaleziono w tablicy
Dowolna liczba od 0 do n-1; oznacza, że element wyszukiwania został znaleziony i zwraca indeks elementu w tablicy. Tutaj „n” oznacza rozmiar tablicy.

Jak działa wyszukiwanie liniowe?

Powiedzmy, że tablica zawiera liczby całkowite. Zadaniem jest znalezienie danej liczby w tablicy.

Jeśli liczba znajduje się w tablicy, musimy zwrócić indeks tej liczby.
Jeśli podana liczba nie zostanie znaleziona, zwróci -1.

Na schemacie blokowym „Dane” to tablica liczb całkowitych, „N” to rozmiar tablicy, a „element” to liczba, którą chcemy przeszukać w tablicy.

Schemat blokowy algorytmu wyszukiwania liniowego:

Oto kroki schematu blokowego:

Krok 1) Przeczytaj wyszukiwany element „przedmiot”.

Krok 2) Zainicjuj i=0 i indeks=-1

Krok 3) Jeśli ja

Krok 4) Jeśli Dane[i] są równe „przedmiotowi”, przejdź do kroku 5. W przeciwnym razie przejdź do kroku 6.

Krok 5) Indeks = i (Ponieważ pozycja znajduje się pod indeksem nr i). Przejdź do kroku 8.

Krok 6) ja = ja +1.

Krok 7) Przejdź do kroku 3.

Krok 8) Stop.

Dla uproszczenia podajemy przykład z tablicą liczb całkowitych. Wyszukiwanie liniowe można również zastosować w ciągu znaków, tablicy obiektów lub strukturze.

Pseudokod algorytmu wyszukiwania sekwencyjnego

function linearSearch: in →Data[], item
foundAt = -1
for i in (0 to data.length): if data[i] equals item
// item is found in the array
// returning the index
return i
// item not found in the array
// -1 means no item found, as negative index is not valid
return -1

C++ Kod Przykładowe wyszukiwanie liniowe

#include < bits / stdc++.h >
    using namespace std;
int linearSearch(int * arr, int item, int n) {
    int idx = -1;
    for (int i = 0; i < n; i++) {
        if (arr[i] == item) {
            idx = i;
            break;
        }
    }
    return idx;
}
int main() {
    int array[] = {
        1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10
    };
    int n = sizeof(array) / sizeof(arr[0]);
    int item;
    cout << "Enter a number to search: ";
    cin >> item;
    int idx = linearSearch(arr, item, n);
    if (idx >= 0) {
        cout << item << " is found at index " << idx << endl;
    } else {
        cout << "Could not find " << item << " in the array" << endl;
    }
}

Wyjście:

Enter a number to search: -10
-10 is found at index 14

Python Kod Przykładowe wyszukiwanie liniowe

def linearSearch(data, item):
    for i in range(len(data)):
    if data[i] == item:
    return i
return -1
data = [1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10]
item = int(input("Enter a number to search: "))
idx = linearSearch(data, item)
if idx >= 0:
    print("{} is found at index {}".format(item, idx))
else :
    print("{} was not found".format(item))

Wyjście:

Enter a number to search: -10
-10 is found at index 14

Analiza złożoności algorytmu wyszukiwania liniowego

Ogólnie rzecz biorąc, złożoność czasowa oznacza ilość czasu procesora potrzebną do wykonania określonego zadania. W algorytmie wyszukiwania liniowego zadaniem jest znalezienie klucza wyszukiwania z elementu tablicy.

Istnieją trzy rodzaje złożoności czasowej:

Najgorszy scenariusz
Najlepszy scenariusz
Przeciętny scenariusz przypadku

Złożoność czasowa wyszukiwania liniowego w najgorszym scenariuszu:

Załóżmy, że musimy przeprowadzić przeszukiwanie liniowe w tablicy o rozmiarze „n”. Szukany element możemy znaleźć w przedziale od 0 do n-1. W najgorszym przypadku algorytm spróbuje dopasować wszystkie elementy tablicy do elementu wyszukiwania.

W takim przypadku złożoność najgorszego przypadku będzie wynosić O(n). Tutaj „O”-big O Notation oznacza funkcję złożoności.

Złożoność czasowa wyszukiwania liniowego w najlepszym scenariuszu:

Załóżmy, że szukamy elementu, który znajduje się na pierwszej pozycji w tablicy. W tym scenariuszu algorytm wyszukiwania liniowego nie będzie szukał wszystkich n elementów w tablicy. Zatem złożoność będzie wynosić O(1). Oznacza to stały czas.

Złożoność czasowa wyszukiwania liniowego w scenariuszu przeciętnego przypadku:

Jeżeli element zostanie znaleziony w środkowym indeksie tablicy, można powiedzieć, że średnia złożoność przypadku dla wyszukiwania liniowego wynosi O(N), gdzie N oznacza długość tablicy.

Złożoność przestrzenna algorytmu wyszukiwania liniowego

Złożoność przestrzenna dla wyszukiwania liniowego zawsze wynosi O(N), ponieważ nie musimy przechowywać ani używać żadnej zmiennej tymczasowej w funkcji wyszukiwania liniowego.

Jak ulepszyć algorytm wyszukiwania liniowego

Wyszukiwanie może być wykonywane wielokrotnie w całym cyklu życia programu. Możliwe jest również, że uruchamiamy liniowy algorytm wyszukiwania i szukamy określonego klucza kilka razy. Możemy użyć „Algorytm wyszukiwania binarnego”, jeśli tablica jest tablicą posortowaną.

Załóżmy, że tablica składa się z 10 tysięcy liczb, a element docelowy znajduje się pod indeksem 5000. Tak więc algorytm spróbuje porównać 5000 elementów. Teraz porównania są zadaniami obciążającymi procesor. Aby zoptymalizować algorytm wyszukiwania liniowego, mamy dwie opcje.

Transpozycja
Przenieś na przód

Transpozycja:

W tej metodzie zamienimy element wyszukiwania z jego poprzednim elementem w tablicy. Na przykład, powiedzmy, że masz tablicę taką jak ta:

Dane[] = {1,5,9,8,7,3,4,11}

Teraz chcemy wyszukać 4. Kroki transpozycji:

Krok 1) „4” znajduje się w indeksie 6. Wymagało to sześciu porównań.

Krok 2) Zamień dane[6] i dane[5]. Następnie tablica danych będzie wyglądać następująco:

Dane[] = {1,5,9,8,7,4,3,11}

Krok 3) Wyszukaj ponownie 4. Znaleziony w indeksie 5. Tym razem potrzeba było pięciu porównań.

Krok 4) Zamień dane [5] i dane [4]. Następnie tablica danych będzie wyglądać następująco:

Dane [] = {1,5,9,8,4,7,3,11}

Teraz, jeśli zauważysz, im częściej przeszukiwany jest klucz, tym bardziej zmniejsza się indeks. W ten sposób zmniejsza się liczba porównań.

Przejdź do przodu:

W tej metodzie zamieniamy element wyszukiwania w indeksie 0. Ponieważ jeśli przeszukamy go ponownie, możemy go znaleźć w czasie O(1).

Zastosowanie algorytmu przeszukiwania liniowego

Oto kilka aplikacji do wyszukiwania liniowego, z których możemy skorzystać.

W przypadku tablic o małych rozmiarach lub tylko kilku elementów na liście łatwiej jest zastosować wyszukiwanie liniowe.
Metodę wyszukiwania liniowego można zastosować w trybie pojedynczym lub tablice wielowymiarowe lub inne struktury danych.
Ogólnie rzecz biorąc, wyszukiwanie liniowe jest proste i skuteczne w przypadku wyszukiwania „nieuporządkowanych” danych. Z podanej listy nieuporządkowanej możemy łatwo pobrać pojedyncze dane.

Możesz lubić: