Lineair zoeken: Python, C++ Voorbeeld

Door: Sara Chen Sara Chen
Hours Bijgewerkt

Wat is een zoekalgoritme?

Een zoekalgoritme is ontworpen om een ​​element of object te vinden uit een verzameling elementen of objecten met een gegeven datastructuur. Zoek bijvoorbeeld naar de minimale hoogte uit een gegeven lijst met hoogtes, of zoek naar het hoogste cijfer uit een lijst of array met getallen. Enkele populaire zoekalgoritmen zijn onder andere "Linear Search", "Binary Search", "Jump Search", "Fibonacci Search", etc.

Wat is lineair zoeken?

Lineair zoeken is een van de eenvoudigste zoekalgoritmen. Vanuit een gegeven lijst of array zoekt het één voor één naar het gegeven element. Lineair zoeken itereert over de hele lijst en controleert of een bepaald element gelijk is aan het zoekelement. Het wordt ook wel de sequentieel zoeken.

Wat doet de lineaire zoekfunctie?

Een array van gehele getallen wordt gegeven als “Numbers,” en een variabele “item” bevat het gehele getal waarnaar moet worden gezocht.

Het lineaire zoekalgoritme kan nu de volgende uitvoer leveren:

  • “-1”; dit betekent dat het gegeven element niet in de array voorkomt
  • Elk getal tussen 0 en n-1; betekent dat het zoekelement is gevonden en retourneert de index van het element in de array. Hier vertegenwoordigt "n" de grootte van de array.

Hoe werkt lineair zoeken?

Laten we zeggen een array met gehele getallen. De taak is om een ​​gegeven getal in de array te vinden.

  • Als het getal zich in de array bevindt, moeten we de index van dat getal retourneren.
  • Als het opgegeven getal niet wordt gevonden, wordt -1 geretourneerd.

In het stroomdiagram is “Data” de integer-array, “N” is de grootte van de array en het “item” is het getal dat we in de array willen zoeken.

Stroomdiagram voor lineair zoekalgoritme:

Stroomdiagram voor lineair zoekalgoritme

Dit zijn de stappen van het stroomdiagram:

Stap 1) Lees het zoekitem 'item'.

Stap 2) Start i=0 en index=-1

Stap 3) Als ik

Stap 4) Als Data[i] gelijk is aan “item”, ga dan naar stap 5. Ga anders naar stap 6.

Stap 5) Index = i (zoals het item te vinden is bij index nr. i). Ga naar stap 8.

Stap 6) ik = ik +1.

Stap 7) Ga naar stap 3.

Stap 8) Stoppen.

Voor de eenvoud geven we een voorbeeld met een array van gehele getallen. Lineair zoeken is ook toepasbaar in de string, een array van objecten of struct.

Pseudocode voor sequentieel zoekalgoritme

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++ Codevoorbeeld Lineair zoeken

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

Output:

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

GERELATEERDE ARTIKELEN

Python Codevoorbeeld Lineair zoeken

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

Output:

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

Complexiteitsanalyse van lineair zoekalgoritme

Over het algemeen betekent tijdcomplexiteit de hoeveelheid CPU-tijd om een ​​bepaalde taak uit te voeren. In het lineaire zoekalgoritme is de taak om de zoeksleutel te vinden in het element van de array.

Er zijn drie soorten tijdcomplexiteiten:

  • In het slechtste geval
  • In het gunstigste geval
  • Gemiddeld casusscenario

Tijdcomplexiteit van lineair zoeken in het worstcasescenario:

Laten we zeggen dat we een lineaire zoekopdracht moeten uitvoeren in een array met de grootte “n”. We kunnen het zoekitem vinden tussen index 0 tot n-1. In het ergste geval zal het algoritme proberen alle elementen uit de array te matchen met het zoekelement.

In dat geval zal de complexiteit in het slechtste geval O(n) zijn. Hierbij betekent de notatie "O"-groot O de complexiteitsfunctie.

Tijdcomplexiteit van lineair zoeken in het beste geval scenario:

Stel dat we zoeken naar een element dat zich op de eerste positie in de array bevindt. In dit scenario zal het lineaire zoekalgoritme niet zoeken naar alle n elementen in de array. Dus de complexiteit zal O(1) zijn. Dit betekent constante tijd.

Tijdcomplexiteit van lineaire zoekopdracht in gemiddeld geval:

Wanneer een element zich op de middelste index van de array bevindt, kan worden gesteld dat de gemiddelde case-complexiteit voor lineair zoeken O(N) is, waarbij N de lengte van de array aangeeft.

De ruimtelijke complexiteit van het lineaire zoekalgoritme

De ruimtecomplexiteit voor de lineaire zoekfunctie is altijd O(N), omdat we geen tijdelijke variabelen hoeven op te slaan of te gebruiken in de lineaire zoekfunctie.

Hoe u het lineaire zoekalgoritme kunt verbeteren

Zoeken kan meerdere keren worden gedaan gedurende de levenscyclus van het programma. Het is ook mogelijk dat we het lineaire zoekalgoritme uitvoeren en meerdere keren naar een specifieke sleutel zoeken. We kunnen de "Binair zoekalgoritme' als de array een gesorteerde array is.

Stel dat de array uit 10 duizend getallen bestaat en dat het doelelement zich op de 5000e index bevindt. Het algoritme zal dus proberen om 5000 elementen te vergelijken. Vergelijkingen zijn CPU-intensieve taken. Om het lineaire zoekalgoritme te optimaliseren, hebben we twee opties.

  • Omzetting
  • Ga naar de voorkant

Omzetting:

In deze methode wisselen we het zoekelement met het vorige element in de array. Stel dat u een array hebt zoals de volgende:

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

Nu willen we 4 stappen van transpositie doorzoeken:

Transpositie bij lineair zoeken

Stap 1) “4” staat bij index 6. Er waren zes vergelijkingen nodig.

Stap 2) Wissel gegevens[6] en gegevens[5] uit. Dan ziet de data-array er als volgt uit:

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

Stap 3) Zoek opnieuw 4. Gevonden bij index 5. Deze keer waren er vijf vergelijkingen nodig.

Stap 4) Wissel gegevens [5] en gegevens [4] uit. De data-array ziet er dan als volgt uit:

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

Als u nu opmerkt: hoe vaker een sleutel wordt doorzocht, hoe meer de index wordt verlaagd. Het aantal vergelijkingen wordt dus verminderd.

Verplaats naar voren:

Bij deze methode wisselen we het zoekelement in de 0e index. Want als er opnieuw naar wordt gezocht, kunnen we het om O(1) tijd vinden.

Ga naar voren in lineair zoeken

Toepassing van lineair zoekalgoritme

Hier zijn enkele lineaire zoektoepassingen die we kunnen gebruiken.

  • Voor kleine arrays of slechts een paar elementen in de lijst is het eenvoudiger om lineair te zoeken.
  • Lineaire zoekmethode kan worden gebruikt in enkele of multidimensionale arrays of andere datastructuren.
  • Over het algemeen is lineair zoeken eenvoudig en efficiënt om een ​​zoekopdracht uit te voeren in de “ongeordende” gegevens. We kunnen eenvoudig enkele gegevens uit de gegeven ongeordende lijst ophalen.