Lineær søgning: Python, C++ Eksempel

Hvad er søgealgoritme?

En søgealgoritme er designet til at finde et element eller objekt fra en samling af elementer eller objekter med en given datastruktur. For eksempel kan man søge efter minimumshøjden fra en given liste over højder, eller søge efter det højeste mærke fra en liste eller et array af tal. Nogle populære søgealgoritmer inkluderer "Lineær søgning", "Binær søgning", "Jump-søgning", "Fibonacci-søgning" osv.

Hvad er lineær søgning?

Lineær søgning er en af ​​de enkleste søgealgoritmer. Fra en given liste eller et given array søger den efter det givne element ét efter ét. Lineær søgning itererer over hele listen og kontrollerer, om et bestemt element er lig med søgeelementet. Det kaldes også sekventiel søgning.

Hvad gør lineær søgefunktion?

En matrix af heltal er givet som "Numbers," og en variabel "item" indeholder det heltal, der skal søges i.

Nu kan den lineære søgealgoritme give følgende output:

• "-1"; dette betyder, at det givne element ikke findes i arrayet.
• Ethvert tal mellem 0 og n-1; betyder, at søgeelementet er fundet, og det returnerer indekset for elementet på arrayet. Her repræsenterer "n" størrelsen af ​​arrayet.

Hvordan virker lineær søgning?

Lad os sige et array, der indeholder heltal. Opgaven er at finde et givet tal i arrayet.

• Hvis tallet er placeret i arrayet, skal vi returnere indekset for dette tal.
• Hvis det givne tal ikke findes, vil det returnere -1.

I rutediagrammet er "Data" heltalsarrayet, "N" er størrelsen på arrayet, og "elementet" er det nummer, vi ønsker at søge i arrayet.

Flowchart for lineær søgealgoritme:

Her er trinene i rutediagrammet:

Trin 1) Læs søgepunktet, "vare".

Trin 2) Initier i=0 og indeks=-1.

Trin 3) Hvis jeg

Trin 4) Hvis Data[i] er lig med "element", så gå til trin 5. Ellers gå til trin 6.

Trin 5) Indeks = i (Da elementet findes ved indeks nr. i). Gå til trin 8.

Trin 6) i = i +1.

Trin 7) Gå til trin 3.

Trin 8) Stop.

For nemheds skyld giver vi et eksempel med en række heltal. Lineær søgning er også anvendelig i strengen, en række objekter eller strukturen.

Kaldenavn Code til sekventiel søgealgoritme

Følgende pseudokode indfanger logikken i den lineære søgning beskrevet ovenfor. Den gennemgår arrayet fra det første indeks og returnerer positionen ved et match, ellers returnerer 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 Eksempel på lineær søgning

Her er en komplet C++ program, der implementerer den sekventielle søgning og udskriver indekset for den søgte værdi.

#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 Eksempel på lineær søgning

Den samme logik i Python bruger et enkelt loop over listeindekserne og returnerer positionen af ​​det matchede 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

Kompleksitetsanalyse af lineær søgealgoritme

Generelt betyder tidskompleksitet den mængde CPU-tid, det tager at udføre en bestemt opgave. I den lineære søgealgoritme er opgaven at finde søgenøglen ud fra elementerne i arrayet.

Tre typer tidskompleksiteter er:

• Værste tilfælde
• Bedste Case Scenario
• Gennemsnitligt tilfælde

Tidskompleksitet af lineær søgning i Worst-Case Scenario:

Lad os sige, at vi skal udføre en lineær søgning i et array med størrelsen "n". Vi kan finde søgeelementet mellem indeks 0 og n-1. I værste fald vil algoritmen forsøge at matche alle elementerne fra arrayet med søgeelementet.

I så fald vil den værst tænkelige kompleksitet være O(n). Her betyder "O" — stor O-notation — kompleksitetsfunktionen.

Tidskompleksitet af lineær søgning i Bedste-Case Scenario:

Lad os sige, at vi søger efter et element, der befinder sig i den første position i arrayet. I dette scenarie vil den lineære søgealgoritme ikke søge efter alle n elementer i arrayet. Så kompleksiteten vil være O(1). Det betyder konstant tid.

Tidskompleksitet af lineær søgning i gennemsnitsscenarie:

Når et element findes ved det midterste indeks af arrayet, så kan man sige, at den gennemsnitlige sagskompleksitet for lineær søgning er O(N), hvor N betyder længden af ​​arrayet.

Rumkompleksiteten af ​​den lineære søgealgoritme:

Rumkompleksiteten for den lineære søgning er altid O(N), fordi vi ikke behøver at gemme eller bruge nogen form for midlertidig variabel i den lineære søgefunktion.

Sådan forbedres lineær søgealgoritme

Søgning kan udføres flere gange i løbet af programmets livscyklus. Det er også muligt, at vi kører den lineære søgealgoritme og søger efter en specifik nøgle flere gange. Vi kan bruge "Binær søgealgoritme” hvis arrayet er et sorteret array.

Antag, at arrayet består af 10 tusinde numre, og at målelementet findes ved det 5000. indeks. Så algoritmen vil forsøge at sammenligne 5000 elementer. Nu er sammenligninger CPU-tunge opgaver. For at optimere den lineære søgealgoritme har vi to muligheder.

• Transponering
• Flyt til fronten

Omrokering:

I denne metode bytter vi søgeelementet ud med dets forrige element i arrayet. Lad os for eksempel sige, at du har et array som det følgende:

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

Nu vil vi søge efter 4. Transponeringstrin:

Trin 1) "4" findes i indeks 6. Det krævede seks sammenligninger.

Trin 2) Byt data[6] og data[5]. Så vil dataarrayet se sådan ud:

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

Trin 3) Søg 4 igen. Fundet ved indeks 5. Denne gang tog det fem sammenligninger.

Trin 4) Byt om på data[5] og data[4]. Datamatrixen vil så se sådan ud:

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

Hvis du bemærker det, jo oftere en nøgle søges, desto mere mindskes indekset. Dermed mindskes antallet af sammenligninger.

Flyt til fronten:

I denne metode bytter vi søgeelementet til det 0. indeks. Fordi hvis det søges igen, kan vi finde det på O(1) tidspunktet.

Anvendelse af lineær søgealgoritme

Her er nogle lineære søgeapplikationer, vi kan bruge.

• For små arrays eller kun få elementer på listen er det nemmere at bruge lineær søgning.
• Lineær søgemetode kan bruges i enkelt eller multidimensionelle arrays eller andre datastrukturer.
• Generelt er lineær søgning enkel og effektiv til at udføre en søgning i de "uordnede" data. Vi kan nemt hente en enkelt data fra den givne uordnede liste.

Ofte Stillede Spørgsmål