Lineair zoeken: Python, C++ voorbeeld

Wat is Searching algoritme?

Een searching-algoritme is ontworpen om een ​​element of object te vinden uit een verzameling elementen of objecten met een bepaalde datastructuur. Zoek bijvoorbeeld de minimale hoogte uit een bepaalde lijst met hoogten, of zoek naar het hoogste cijfer uit een lijst of reeks getallen. Weinig populaire searching-algoritmen omvatten "Lineair zoeken", "Binair zoeken", "Jump zoeken", "Fibonacci zoeken", enz.

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 herhaalt 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 ‘Getallen’, en een variabele ‘item’ bevat het gehele getal waarnaar moet worden gezocht.

Nu kan het Linear Search-algoritme het volgende biedenwing output:

  • “-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 ​​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:

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

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 is tijd complexity betekent de hoeveelheid CPU-tijd om een ​​bepaalde taak uit te voeren. Bij het lineaire zoekalgoritme is het de taak om de zoeksleutel uit het element van de array te vinden.

Drie soorten tijd complexiteiten zijn:

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

Tijd Complexkwaliteit van lineair zoeken in het slechtste scenario:

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 is het worst-case complexiteit zal O(n) zijn. Hier betekent “O”-big O-notatie de complexity-functie.

Tijd Complexkwaliteit van lineair zoeken in het beste scenario:

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

Tijd Complexiteit van lineair zoeken in gemiddeld gevalscenario:

Wanneer een element wordt gevonden in de middelste index van de array, kan worden gezegd dat het gemiddelde geval complexDe waarde voor lineair zoeken is O(N), waarbij N de lengte van de array betekent.

De ruimte complexvan het lineaire zoekalgoritme

Ruimte complexDe eigenschap voor de lineaire zoekactie is altijd O(N), omdat we geen enkele tijdelijke variabele hoeven op te slaan of te gebruiken in de lineaire zoekfunctie.

Hoe u het lineaire zoekalgoritme kunt verbeteren

Er kan tijdens de levenscyclus van het programma meerdere keren worden gezocht. Het is ook mogelijk dat we het lineaire zoekalgoritme gebruiken en searchimeerdere keren voor een specifieke sleutel. Wij kunnen gebruik maken van de “Binair zoekalgoritme' als de array een gesorteerde array is.

Stel dat de array uit 10 getallen bestaat en dat het doelelement op de 5000e index staat. Het algoritme zal dus proberen 5000 elementen te vergelijken. Nu zijn vergelijkingen CPU-zware taken. Om het lineaire zoekalgoritme te optimaliseren, hebben we twee opties.

  • Omzetting
  • Ga naar de voorkant

Omzetting:

Bij deze methode wisselen we het zoekelement met het vorige element in de array. Stel dat u bijvoorbeeld een array heeft zoals de following:

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.