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 un obiect dintr-o colecție de elemente sau obiecte cu o anumită structură de date. De exemplu, se poate căuta înălțimea minimă dintr-o listă dată de înălțimi sau se poate căuta cea mai mare notă dintr-o listă sau o matrice de numere. Printre algoritmii de căutare populari se numără „Căutare liniară”, „Căutare binară”, „Căutare prin salt”, „Căutare Fibonacci” etc.

Ce este căutarea liniară?

Căutare liniară este unul dintre cei mai simpli algoritmi de căutare. Dintr-o listă sau un tablou dat, caută elementul dat unul câte unul. Căutarea liniară iterează peste î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 matrice.
• 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țiați 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 elementul 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.

Pseudo Code pentru algoritmul de căutare secvențială

Următorul pseudocod surprinde logica căutării liniare descrise mai sus. Parcurge matricea de la primul index și returnează poziția la o potrivire, altfel returnează -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 Exemplu de căutare liniară

Iată un complet C++ program care implementează căutarea secvențială și afișează indexul valorii căutate.

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

ieșire:

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

Python Code Exemplu de căutare liniară

Aceeași logică în Python folosește o singură buclă peste indicii listei și returnează poziția elementului potrivit.

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 temporală înseamnă timpul CPU necesar pentru a efectua o anumită sarcină. În algoritmul de căutare liniară, sarcina este de a găsi cheia de căutare din elementele 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-un tablou cu dimensiunea „n”. Putem găsi elementul de căutare între indexul 0 și n-1. În cel mai rău caz, algoritmul va încerca să potrivească toate elementele din tablou cu elementul de căutare.

În acest caz, complexitatea cea mai defavorabilă va fi O(n). Aici, „O” — notația O mare — î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ă pe prima poziție a tabloului. În acest scenariu, algoritmul de căutare liniară nu va căuta toate cele n elemente din tablou. 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țială pentru căutarea liniară este întotdeauna O(N) deoarece nu este nevoie să stocăm sau să folosim niciun 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 o cheie specifică de mai multe ori. 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 data[5] și data[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 des, cu atât indexul scade. Astfel, scade numărul de comparații.

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

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

Aplicarea algoritmului de căutare liniară

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

• Pentru tablouri de dimensiuni mici sau doar pentru câteva elemente din listă, este mai ușor să se utilizeze 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ă.

Întrebări frecvente