Linjär sökning: Python, C++ Exempelvis

Vad är sökalgoritm?

En sökalgoritm är utformad för att hitta ett element eller objekt från en samling element eller objekt med en given datastruktur. Sök till exempel den lägsta höjden från en given lista med höjder, eller sök efter den högsta markeringen från en lista eller rad med nummer. Några populära sökalgoritmer inkluderar "Linjär sökning", "Binär sökning", "Jump Search", "Fibonacci Search" etc.

Vad är linjär sökning?

Linjär sökning är en av de enklaste sökalgoritmerna. Från en given lista eller array söker den efter det givna elementet en efter en. Linjär sökning itererar över hela listan och kontrollerar om något särskilt element är lika med sökelementet. Det kallas också för sekventiell sökning.

Vad gör linjär sökfunktion?

En matris med heltal ges som "Numbers," och en variabel "objekt" innehåller det heltal som ska sökas.

Nu kan den linjära sökalgoritmen ge följande utdata:

• "-1"; detta betyder att det givna elementet inte finns i arrayen
• Valfritt tal mellan 0 till n-1; betyder att sökelementet hittas, och det returnerar indexet för elementet i arrayen. Här representerar "n" storleken på arrayen.

Hur fungerar linjär sökning?

Låt oss säga en array som innehåller heltal. Uppgiften är att hitta ett givet nummer i arrayen.

• Om numret finns i arrayen måste vi returnera indexet för det numret.
• Om det givna numret inte hittas, kommer det att returnera -1.

I flödesschemat är "Data" heltalsmatrisen, "N" är storleken på matrisen och "objektet" är numret vi vill söka i matrisen.

Flödesschema för linjär sökalgoritm:

Här är stegen i flödesschemat:

Steg 1) Läs sökobjektet, "artikel".

Steg 2) Initiera i=0 och index=-1

Steg 3) Om jag

Steg 4) Om Data[i] är lika med "objekt", gå till steg 5. Gå annars till steg 6.

Steg 5) Index = i (Eftersom artikeln finns vid index nr i). Gå till steg 8.

Steg 6) i = i +1.

Steg 7) Gå till steg 3.

Steg 8) Sluta.

För enkelhetens skull ger vi ett exempel med en uppsättning heltal. Linjär sökning är också användbar i strängen, en array av objekt eller struktur.

Pseudokod för sekventiell sökalgoritm

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++ Kodexempel Linjär sökning

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

Produktion:

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

Python Kodexempel Linjär sökning

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

Produktion:

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

Komplexitetsanalys av linjär sökalgoritm

I allmänhet betyder tidskomplexitet mängden CPU-tid för att utföra en viss uppgift. I den linjära sökalgoritmen är uppgiften att hitta söknyckeln från elementet i arrayen.

Tre typer av tidskomplexitet är:

• I värsta fall
• Best Case Scenario
• Genomsnittligt fallscenario

Tidskomplexiteten för linjär sökning i värsta fall:

Låt oss säga att vi måste utföra en linjär sökning i en matris med storleken "n". Vi kan hitta sökobjektet mellan index 0 till n-1. I värsta fall kommer algoritmen att försöka matcha alla element från arrayen med sökelementet.

I så fall kommer komplexiteten i värsta fall att vara O(n). Här betyder "O"-big O Notation komplexitetsfunktionen.

Tidskomplexiteten för linjär sökning i bästa fallscenario:

Låt oss säga att vi söker efter ett element som finns i den första positionen i arrayen. I det här scenariot kommer den linjära sökalgoritmen inte att söka efter alla n element i arrayen. Så komplexiteten blir O(1). Det betyder konstant tid.

Tidskomplexitet för linjär sökning i genomsnittligt fallscenario:

När ett element hittas i mittindexet av arrayen kan man säga att den genomsnittliga case-komplexiteten för linjär sökning är O(N), där N betyder längden på arrayen.

Rymdkomplexiteten för den linjära sökalgoritmen

Utrymmeskomplexiteten för den linjära sökningen är alltid O(N) eftersom vi inte behöver lagra eller använda någon form av temporär variabel i den linjära sökfunktionen.

Hur man förbättrar linjär sökalgoritm

Sökning kan göras flera gånger under programmets livscykel. Det är också möjligt att vi kör den linjära sökalgoritmen och söker efter någon specifik nyckel flera gånger. Vi kan använda "Binär sökalgoritm” om arrayen är en sorterad array.

Antag att arrayen består av 10 tusen tal, och målelementet finns vid det 5000:e indexet. Så, algoritmen kommer att försöka jämföra 5000 element. Nu är jämförelser processortunga uppgifter. För att optimera den linjära sökalgoritmen har vi två alternativ.

• Transposition
• Flytta till fronten

Transponering:

I den här metoden kommer vi att byta sökelementet med dess tidigare element i arrayen. Låt oss till exempel säga att du har en array som följande:

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

Nu vill vi söka efter 4. Transponeringssteg:

Steg 1) "4" finns i index 6. Det krävdes sex jämförelser.

Steg 2) Byt data[6] och data[5]. Då kommer datamatrisen att se ut så här:

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

Steg 3) Sök 4 igen. Hittade vid index 5. Den här gången tog det fem jämförelser.

Steg 4) Byt data [5] och data[4]. Då kommer datamatrisen att se ut så här:

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

Nu, om du märker att ju oftare en nyckel genomsöks, desto mer minskar indexet. Alltså minskar antalet jämförelser.

Flytta till fronten:

I den här metoden byter vi sökelementet i det 0:e indexet. För om den söks igen kan vi hitta den vid O(1) tid.

Tillämpning av linjär sökalgoritm

Här är några linjära sökapplikationer vi kan använda.

• För små arrayer eller bara några få element i listan är det lättare att använda linjär sökning.
• Linjär sökmetod kan användas i enkel eller flerdimensionella arrayer eller andra datastrukturer.
• I allmänhet är linjär sökning enkel och effektiv för att utföra en sökning i "oordnad" data. Vi kan enkelt hämta en enda data från den givna oordnade listan.