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. Till exempel, sök efter den minsta höjden från en given lista med höjder, eller sök efter det högsta märket från en lista eller array med tal. Några populära sökalgoritmer inkluderar "Linjär sökning", "Binär sökning", "Hoppsökning", "Fibonaccisökning" 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 ett i taget. Linjär sökning itererar över hela listan och kontrollerar om något visst element är lika med sökelementet. Det kallas också 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 tal 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 objektet finns vid indexnummer 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.

Pseudo Code för sekventiell sökalgoritm

Följande pseudokod fångar logiken i den linjära sökning som beskrivs ovan. Den går igenom arrayen från det första indexet och returnerar positionen vid en matchning, annars returnerar den -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 Exempel på linjär sökning

Här är en komplett C++ program som implementerar den sekventiella sökningen och skriver ut indexet för det sökta värdet.

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

Produktion:

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

Python Code Exempel på linjär sökning

Samma logik i Python använder en enda loop över listindexen och returnerar positionen för det matchade elementet.

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

Generellt sett betyder tidskomplexitet den mängd CPU-tid som krävs för att utföra en viss uppgift. I den linjära sökalgoritmen är uppgiften att hitta söknyckeln från elementen 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 behöver utföra en linjär sökning i en array med storleken "n". Vi kan hitta sökelementet mellan index 0 och n-1. I värsta fall kommer algoritmen att försöka matcha alla element från arrayen med sökelementet.

I så fall blir den värsta tänkbara komplexiteten O(n). Här betyder "O" — stor 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). Detta 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 hos den linjära sökalgoritmen:

Rumskomplexiteten för linjär sökning ä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 en 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 byter vi ut sökelementet mot dess föregående element i arrayen. Låt oss till exempel säga att du har en array som den här:

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 ut data[5] och data[4]. Datamatrisen kommer då att se ut så här:

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

Om du nu märker det, ju oftare en nyckel söks igenom, desto mer minskar indexet. Därmed minskar antalet jämförelser.

Flytta till fronten:

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

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 ett fåtal element i listan är det enklare 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.

Vanliga frågor