Linearno pretraživanje: Python, C++ Primjer

Što je algoritam pretraživanja?

Algoritam pretraživanja osmišljen je za pronalaženje elementa ili objekta iz zbirke elemenata ili objekata s danom strukturom podataka. Na primjer, pretraživanje minimalne visine s danog popisa visina ili pretraživanje najviše oznake s popisa ili niza brojeva. Nekoliko popularnih algoritama pretraživanja uključuje "linearno pretraživanje", "binarno pretraživanje", "pretragu sa skokom", "Fibonaccijevo pretraživanje" itd.

Što je linearno pretraživanje?

Linearno pretraživanje je jedan od najjednostavnijih algoritama pretraživanja. Iz zadanog popisa ili niza pretražuje zadane elemente jedan po jedan. Linearno pretraživanje iterira kroz cijeli popis i provjerava je li bilo koji određeni element jednak traženom elementu. Također se naziva i sekvencijalno pretraživanje.

Što radi funkcija linearnog pretraživanja?

Niz cijelih brojeva zadan je kao "Numbers,” a varijabla “item” sadrži cijeli broj za pretraživanje.

Sada, algoritam linearnog pretraživanja može dati sljedeći rezultat:

• „-1“; to znači da se zadani element ne nalazi u nizu.
• Bilo koji broj između 0 do n-1; znači da je traženi element pronađen i vraća indeks elementa u nizu. Ovdje "n" predstavlja veličinu niza.

Kako radi linearno pretraživanje?

Recimo da je niz koji sadrži cijele brojeve. Zadatak je pronaći zadani broj u nizu.

• Ako se broj nalazi u nizu, moramo vratiti indeks tog broja.
• Ako zadani broj nije pronađen, vratit će -1.

U dijagramu toka, "Podaci" su niz cijelih brojeva, "N" je veličina niza, a "stavka" je broj koji želimo pretraživati ​​u nizu.

Dijagram toka za algoritam linearnog pretraživanja:

Evo koraka dijagrama toka:

Korak 1) Pročitajte stavku pretraživanja, "stavka".

Korak 2) Inicijalizirajte i=0 i indeks=-1.

Korak 3) Ako ja

Korak 4) Ako je Data[i] jednako "item", tada idite na korak 5. Inače idite na korak 6.

Korak 5) Indeks = i (Budući da se stavka nalazi na indeksu br. i). Idi na korak 8.

Korak 6) i = i +1.

Korak 7) Idite na korak 3.

Korak 8) Zaustavite.

Radi jednostavnosti, dajemo primjer s nizom cijelih brojeva. Linearno pretraživanje također je primjenjivo u nizu, nizu objekata ili strukturi.

Nadimak Code za algoritam sekvencijalnog pretraživanja

Sljedeći pseudokod obuhvaća logiku linearnog pretraživanja opisanog gore. Obilazi niz od prvog indeksa i vraća poziciju na podudarnosti, inače vraća -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 Primjer linearnog pretraživanja

Evo je potpuni C++ program koji implementira sekvencijalno pretraživanje i ispisuje indeks tražene vrijednosti.

#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;
    }
}

Izlaz:

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

Python Code Primjer linearnog pretraživanja

Ista logika u Python koristi jednu petlju preko indeksa liste i vraća poziciju odgovarajućeg elementa.

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))

Izlaz:

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

Analiza složenosti algoritma linearnog pretraživanja

Općenito, vremenska složenost znači količinu CPU vremena potrebnog za izvršavanje određenog zadatka. U linearnom algoritmu pretraživanja, zadatak je pronaći ključ pretraživanja iz elemenata niza.

Tri vrste vremenske složenosti su:

• Najgori scenarij
• Najbolji scenarij
• Scenarij prosječnog slučaja

Vremenska složenost linearne pretrage u najgorem scenariju:

Recimo da trebamo izvršiti linearno pretraživanje u nizu veličine "n". Možemo pronaći traženi element između indeksa 0 i n-1. U najgorem slučaju, algoritam će pokušati pronaći sve elemente iz niza koji odgovaraju traženom elementu.

U tom slučaju, najgora moguća složenost bit će O(n). Ovdje „O“ — oznaka velikog O — označava funkciju složenosti.

Vremenska složenost linearne pretrage u scenariju najboljeg slučaja:

Recimo da tražimo element koji se nalazi na prvoj poziciji niza. U ovom scenariju, linearni algoritam pretraživanja neće tražiti svih n elemenata u nizu. Dakle, složenost će biti O(1). To znači konstantno vrijeme.

Vremenska složenost linearne pretrage u prosječnom slučaju:

Kada se element nađe na srednjem indeksu niza, tada se može reći da je prosječna složenost slučaja za linearno pretraživanje O(N), gdje N označava duljinu niza.

Prostorna složenost linearnog algoritma pretraživanja:

Prostorna složenost za linearno pretraživanje je uvijek O(N) jer ne moramo pohranjivati ​​ili koristiti bilo kakvu privremenu varijablu u funkciji linearnog pretraživanja.

Kako poboljšati algoritam linearnog pretraživanja

Pretraživanje se može izvršiti više puta tijekom životnog ciklusa programa. Također je moguće da pokrećemo linearni algoritam pretraživanja i tražimo bilo koji određeni ključ nekoliko puta. Možemo koristiti "Algoritam binarnog pretraživanja” ako je polje sortirano polje.

Pretpostavimo da se niz sastoji od 10 tisuća brojeva, a ciljni element se nalazi na 5000. indeksu. Dakle, algoritam će pokušati usporediti 5000 elemenata. Sada su usporedbe teški zadaci CPU-a. Za optimizaciju algoritma linearnog pretraživanja imamo dvije mogućnosti.

• Transpozicija
• Pomakni naprijed

Transpozicija:

U ovoj metodi zamijenit ćemo element pretraživanja s njegovim prethodnim elementom u nizu. Na primjer, recimo da imate niz poput sljedećeg:

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

Sada želimo pretražiti 4. koraka transpozicije:

Korak 1) “4” se nalazi na indeksu 6. Bilo je potrebno šest usporedbi.

Korak 2) Zamijenite podatke[6] i podatke[5]. Tada će niz podataka izgledati ovako:

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

Korak 3) Ponovno pretražite 4. Pronađeno u indeksu 5. Ovaj put je bilo potrebno pet usporedbi.

Korak 4) Zamijenite podatke[5] i podatke[4]. Tada će niz podataka izgledati ovako:

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

Ako primijetite, što se češće traži ključ, to se više smanjuje indeks. Time se smanjuje i broj usporedbi.

Pomakni naprijed:

U ovoj metodi mijenjamo element pretraživanja na 0. indeks. Jer ako se ponovno pretražuje, možemo ga pronaći u vremenu O(1).

Primjena algoritma linearnog pretraživanja

Evo nekoliko aplikacija za linearno pretraživanje koje možemo koristiti.

• Za male nizove ili samo nekoliko elemenata na popisu, lakše je koristiti linearno pretraživanje.
• Metoda linearnog pretraživanja može se koristiti u jednom ili višedimenzionalni nizovi ili druge strukture podataka.
• Općenito, linearna pretraga je jednostavna i učinkovita za pretraživanje u "neuređenim" podacima. Lako možemo dohvatiti jedan podatak s danog nesređenog popisa.

Pitanja i odgovori