Wyszukiwanie liniowe: Python, C++ Przykład

Czym jest algorytm wyszukiwania?

Algorytm wyszukiwania służy do wyszukiwania elementu lub obiektu w zbiorze elementów lub obiektów o zadanej strukturze danych. Na przykład, wyszukaj minimalną wysokość z podanej listy wysokości lub wyszukaj najwyższy znak z listy lub tablicy liczb. Kilka popularnych algorytmów wyszukiwania to „wyszukiwanie liniowe”, „wyszukiwanie binarne”, „wyszukiwanie skokowe”, „wyszukiwanie Fibonacciego” itp.

Co to jest wyszukiwanie liniowe?

Wyszukiwanie liniowe to jeden z najprostszych algorytmów wyszukiwania. Na podanej liście lub tablicy wyszukuje po kolei dany element. Wyszukiwanie liniowe iteruje po całej liście i sprawdza, czy którykolwiek element jest równy szukanemu elementowi. Nazywa się je również 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 dany element nie został znaleziony 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?

Załóżmy, że mamy tablicę zawierającą liczby całkowite. Zadanie polega na znalezieniu 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ż element znajduje się pod indeksem 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.

Rzekomy Code dla algorytmu wyszukiwania sekwencyjnego

Poniższy pseudokod oddaje logikę wyszukiwania liniowego opisanego powyżej. Przechodzi on przez tablicę od pierwszego indeksu i zwraca pozycję w dopasowaniu, w przeciwnym razie zwraca -1.

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 a negative index is not valid
    return -1

C++ Code Przykładowe wyszukiwanie liniowe

Oto kompletny C++ program implementujący sekwencyjne wyszukiwanie i wyświetlający indeks poszukiwanej wartości.

#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(array[0]);
    int item;
    cout << "Enter a number to search: ";
    cin >> item;
    int idx = linearSearch(array, 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 Code Przykładowe wyszukiwanie liniowe

Ta sama logika w Python używa pojedynczej pętli po indeksach listy i zwraca pozycję dopasowanego elementu.

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 spośród elementów 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ć wyszukiwanie liniowe w tablicy o rozmiarze „n”. Możemy znaleźć szukany element między indeksami od 0 do n-1. W najgorszym przypadku algorytm spróbuje dopasować wszystkie elementy tablicy do szukanego elementu.

W takim przypadku złożoność w najgorszym przypadku wyniesie O(n). Tutaj „O” – notacja dużego O – 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 tablicy. W tym scenariuszu algorytm wyszukiwania liniowego nie przeszuka wszystkich n elementó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żna przeprowadzić wielokrotnie w całym cyklu życia programu. Możliwe jest również, że uruchomimy algorytm wyszukiwania liniowego i wyszukamy dowolny klucz wielokrotnie. 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 poprzednim elementem w tablicy. Załóżmy na przykład, że masz tablicę taką jak poniżej:

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]. Wtedy tablica danych będzie wyglądać tak:

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

Zauważ, że im częściej wyszukiwany jest klucz, tym bardziej zmniejsza się indeks. A tym samym zmniejsza się liczba porównań.

Przejdź do przodu:

W tej metodzie zamieniamy szukany element na indeks 0. Ponieważ jeśli zostanie on ponownie przeszukany, znajdziemy go w czasie O(1).

Zastosowanie algorytmu przeszukiwania liniowego

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

• W przypadku tablic o niewielkich rozmiarach lub gdy lista zawiera tylko kilka elementów, ł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.

FAQ