Căutare liniară: Python, C++ Exemplu

Ce este algoritmul de căutare?

Un algoritm de căutare este conceput pentru a găsi un element sau obiect dintr-o colecție de elemente sau obiecte cu o structură de date dată. De exemplu, căutați înălțimea minimă dintr-o listă dată de înălțimi sau căutați cel mai înalt punct dintr-o listă sau dintr-o matrice de numere. Puțini algoritmi de căutare populari includ „Căutare liniară”, „Căutare binară”, „Căutare cu salt”, „Căutare Fibonacci” etc.

Ce este căutarea liniară?

Căutarea liniară este unul dintre cei mai simpli algoritmi de căutare. Dintr-o listă sau o matrice dată, caută unul câte unul elementul dat. Căutarea liniară iterează pe întreaga listă și verifică dacă un anumit element este egal cu elementul de căutare. Se mai numește și căutare secvențială.

Ce face funcția de căutare liniară?

O matrice de numere întregi este dată ca „Numbers”, iar o variabilă „articol” conține numărul întreg de căutat.

Acum, algoritmul de căutare liniară poate oferi următoarele rezultate:

„-1”; aceasta înseamnă că elementul dat nu se găsește în tablou
Orice număr între 0 și n-1; înseamnă că elementul de căutare este găsit și returnează indexul elementului din matrice. Aici, „n” reprezintă dimensiunea matricei.

Cum funcționează Căutarea liniară?

Să presupunem o matrice care conține numere întregi. Sarcina este de a găsi un număr dat în matrice.

Dacă numărul se află în matrice, trebuie să returnăm indexul acelui număr.
Dacă numărul dat nu este găsit, atunci va returna -1.

În diagramă, „Date” este matricea întregi, „N” este dimensiunea matricei, iar „articolul” este numărul pe care vrem să-l căutăm în matrice.

Diagramă pentru algoritmul de căutare liniară:

Iată pașii diagramei:

Pas 1) Citiți elementul de căutare, „articol”.

Pas 2) Inițiază i=0 și index=-1

Pas 3) Dacă eu

Pas 4) Dacă Data[i] este egal cu „articol”, atunci treceți la pasul 5. În caz contrar, mergeți la pasul 6.

Pas 5) Index = i (Deoarece articolul se găsește la indexul nr. i). Treceți la pasul 8.

Pas 6) i = i +1.

Pas 7) Continuați cu pasul 3.

Pas 8) Stop.

Pentru simplitate, oferim un exemplu cu o matrice de numere întregi. Căutarea liniară este aplicabilă și în șir, o matrice de obiecte sau struct.

Pseudocod pentru algoritmul de căutare secvențială

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++ Exemplu de cod Căutare liniară

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

ieșire:

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

Python Exemplu de cod Căutare liniară

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

ieșire:

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

Analiza complexității algoritmului de căutare liniară

În general, complexitatea timpului înseamnă cantitatea de timp CPU pentru a efectua o anumită sarcină. În algoritmul de căutare liniară, sarcina este de a găsi cheia de căutare din elementul matricei.

Trei tipuri de complexități de timp sunt:

În cel mai rău caz
Cel mai bun scenariu
Scenariu mediu de caz

Timp Complexitatea căutării liniare în scenariul cel mai rău caz:

Să presupunem că trebuie să efectuăm o căutare liniară într-o matrice cu dimensiunea „n”. Putem găsi elementul de căutare între indexul 0 la n-1. În cel mai rău caz, algoritmul va încerca să potrivească toate elementele din matrice cu elementul de căutare.

În acest caz, complexitatea în cel mai rău caz va fi O(n). Aici, „O”-big O Notația înseamnă funcția de complexitate.

Timp Complexitatea căutării liniare în scenariul cel mai bun caz:

Să presupunem că căutăm un element care se află în prima poziție la matrice. În acest scenariu, algoritmul de căutare liniară nu va căuta toate cele n elemente din matrice. Deci complexitatea va fi O(1). Aceasta înseamnă timp constant.

Timp Complexitatea căutării liniare în scenariul de caz mediu:

Când un element este găsit la indexul mijlociu al matricei, atunci se poate spune că complexitatea medie a cazului pentru căutarea liniară este O(N), unde N înseamnă lungimea matricei.

Complexitatea spațială a algoritmului de căutare liniară

Complexitatea spațiului pentru căutarea liniară este întotdeauna O(N), deoarece nu trebuie să stocăm sau să folosim nici un fel de variabilă temporară în funcția de căutare liniară.

Cum să îmbunătățiți algoritmul de căutare liniară

Căutarea poate fi efectuată de mai multe ori pe parcursul ciclului de viață al programului. De asemenea, este posibil să rulăm algoritmul de căutare liniară și să căutăm de mai multe ori orice cheie specifică. Putem folosi „Algoritmul de căutare binar” dacă matricea este o matrice sortată.

Să presupunem că matricea constă din 10 mii de numere, iar elementul țintă se găsește la indexul 5000. Deci, algoritmul va încerca să compare 5000 de elemente. Acum, comparațiile sunt sarcini grele pentru CPU. Pentru a optimiza algoritmul de căutare liniară, avem două opțiuni.

Transpunere
Mutați în față

Transpunere:

În această metodă, vom schimba elementul de căutare cu elementul său anterior din matrice. De exemplu, să presupunem că aveți o matrice ca următoarea:

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

Acum, vrem să căutăm 4. Etapele transpunerii:

Pas 1) „4” se găsește la indicele 6. Au fost necesare șase comparații.

Pas 2) Schimbați datele[6] și datele[5]. Apoi matricea de date va arăta astfel:

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

Pas 3) Caută din nou 4. Găsit la indicele 5. De data aceasta a fost nevoie de cinci comparații.

Pas 4) Schimbați datele [5] și datele[4]. Apoi matricea de date va arăta astfel:

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

Acum, dacă observați, cu cât o cheie este căutată mai frecvent, cu atât scade indexul. Astfel, scăderea numărului de comparații.

Deplasați-vă în față:

În această metodă, schimbăm elementul de căutare în indexul 0. Pentru că dacă este căutat din nou, îl putem găsi la ora O(1).

Aplicarea algoritmului de căutare liniară

Iată câteva aplicații de căutare liniară pe care le putem folosi.

Pentru matrice de dimensiuni mici sau doar pentru câteva elemente din listă, este mai ușor să utilizați căutarea liniară.
Metoda de căutare liniară poate fi utilizată în mod simplu sau tablouri multidimensionale sau alte structuri de date.
În general, căutarea liniară este simplă și eficientă pentru a efectua o căutare în datele „neordonate”. Putem prelua cu ușurință o singură dată din lista neordonată dată.