Lineair zoeken: Python, C++ Voorbeeld

Wat is een zoekalgoritme?

Een zoekalgoritme is ontworpen om een ​​element of object te vinden in een verzameling elementen of objecten met een bepaalde datastructuur. Bijvoorbeeld: zoek de minimale hoogte in een lijst met hoogtes, of zoek het hoogste getal in een lijst of array met getallen. Enkele populaire zoekalgoritmen zijn "Lineair zoeken", "Binair zoeken", "Sprongzoeken", "Fibonacci-zoeken", enzovoort.

Wat is lineair zoeken?

Lineair zoeken Lineair zoeken is een van de eenvoudigste zoekalgoritmen. Het zoekt in een gegeven lijst of array naar het opgegeven element, één voor één. Lineair zoeken doorloopt de hele lijst en controleert of een bepaald element gelijk is aan het gezochte element. Het wordt ook wel de sequentiële zoekopdracht.

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 opgegeven 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?

Stel, we hebben een array met gehele getallen. De taak is om een ​​bepaald 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:

Dit zijn de stappen van het stroomdiagram:

Stap 1) Lees het zoekitem 'item'.

Stap 2) Initialiseer 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 (Omdat het item zich op indexnummer i bevindt). 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.

Pseudo Code voor sequentieel zoekalgoritme

De volgende pseudocode beschrijft de logica van de hierboven beschreven lineaire zoekmethode. De code doorloopt de array vanaf de eerste index en retourneert de positie bij een overeenkomst; anders retourneert de code -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 Voorbeeld lineair zoeken

Hier is een complete C++ Een programma dat de sequentiële zoekfunctie implementeert en de index van de gevonden waarde afdrukt.

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

Output:

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

Python Code Voorbeeld lineair zoeken

Dezelfde logica in Python De functie gebruikt één enkele lus over de indexen van de lijst en retourneert de positie van het overeenkomende element.

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 geeft tijdcomplexiteit de hoeveelheid CPU-tijd aan die nodig is om een ​​bepaalde taak uit te voeren. Bij het lineaire zoekalgoritme is de taak het vinden van de zoeksleutel in de elementen 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:

Stel dat we een lineaire zoekopdracht moeten uitvoeren in een array met de grootte "n". We kunnen het gezochte element vinden tussen index 0 en n-1. In het slechtste geval zal het algoritme proberen alle elementen in de array te matchen met het gezochte element.

In dat geval is de complexiteit in het ergste geval O(n). Hier staat "O" — de grote O-notatie — voor de complexiteitsfunctie.

Tijdcomplexiteit van lineair zoeken in het beste geval scenario:

Stel dat we op zoek zijn naar een element dat zich op de eerste positie van de array bevindt. In dit scenario zal het lineaire zoekalgoritme niet alle n elementen in de array doorzoeken. De complexiteit zal dus 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 ruimtecomplexiteit van het lineaire zoekalgoritme:

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

Hoe u het lineaire zoekalgoritme kunt verbeteren

Zoeken kan meerdere keren gedurende de levenscyclus van het programma plaatsvinden. Het is ook mogelijk dat we het lineaire zoekalgoritme meerdere keren uitvoeren en 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:

Bij deze methode wisselen we het gezochte element met het voorgaande element in de array. Stel bijvoorbeeld dat je een array hebt zoals de volgende:

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

Nu willen we 4 stappen van transpositie doorzoeken:

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 data[5] en data[4] om. Dan ziet de data-array er als volgt uit:

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

Zoals je ziet, geldt: hoe vaker er naar een sleutel wordt gezocht, hoe lager de index wordt. Daardoor neemt het aantal vergelijkingen af.

Verplaats naar voren:

Bij deze methode verplaatsen we het zoekelement naar de 0e index. Als we er dan opnieuw naar zoeken, kunnen we het in O(1) tijd vinden.

Toepassing van lineair zoekalgoritme

Hier zijn enkele lineaire zoektoepassingen die we kunnen gebruiken.

• Voor kleine arrays of lijsten met slechts enkele elementen is lineair zoeken eenvoudiger.
• 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.

Veelgestelde vragen