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žite minimalnu visinu s danog popisa visina ili potražite najvišu ocjenu s popisa ili niza brojeva. Nekoliko popularnih algoritama pretraživanja uključuje "Linearno pretraživanje", "Binarno pretraživanje", "Preskočno pretraživanje", "Fibonaccijevo pretraživanje" itd.

Što je linearno pretraživanje?

Linearna pretraga jedan je od najjednostavnijih algoritama pretrage. Iz zadane liste ili niza, traži zadani element jedan po jedan. Linearno pretraživanje ponavlja cijeli popis i provjerava je li neki 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 dati element nije pronađen 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 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:

Dijagram toka za algoritam linearnog pretraživanja

Evo koraka dijagrama toka:

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

Korak 2) Pokreni 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 predmet nalazi pod indeksom br. i). Idite 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.

Pseudo kod za algoritam sekvencijalnog pretraživanja

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++ Linearno pretraživanje primjera koda

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

Izlaz:

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

Python Linearno pretraživanje primjera koda

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 za obavljanje određenog zadatka. U algoritmu linearnog pretraživanja zadatak je pronaći ključ pretraživanja iz elementa 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, trebamo izvršiti linearno pretraživanje u nizu veličine “n”. Stavku za pretraživanje možemo pronaći između indeksa 0 do n-1. U najgorem slučaju, algoritam će pokušati spojiti sve elemente iz niza s traženim elementom.

U tom slučaju, složenost u najgorem slučaju bit će O(n). Ovdje "O"-veliko 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 prvom mjestu u nizu. U ovom scenariju algoritam linearnog pretraživanja neće pretraživati ​​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 algoritma linearnog pretraživanja

Složenost prostora za linearno pretraživanje uvijek je O(N) jer ne trebamo pohranjivati ​​niti 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 algoritam linearnog 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 traženi element 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:

Transpozicija u linearnom pretraživanju

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}

Sada, ako primijetite, što se ključ češće pretražuje, to više smanjuje indeks. Dakle, smanjuje se broj usporedbi.

Pomakni naprijed:

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

Pomaknite se naprijed u linearnom pretraživanju

Primjena algoritma linearnog pretraživanja

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

  • Za nizove male veličine 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.