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

Af: Sarah Chen Sarah Chen
Hours Opdateret

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. Søg f.eks. efter minimumshøjden fra en given liste over højder, eller søg efter den højeste markering fra en liste eller række af tal. Få populære søgealgoritmer inkluderer "Lineær søgning", "Binær søgning", "Jump Search", "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 array søger den efter det givne element én efter én. 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"; det 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 en matrix, 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:

Flowchart for lineær søgealgoritme

Her er trinene i rutediagrammet:

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

Trin 2) Start 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 varen 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.

Pseudokode til sekventiel søgealgoritme

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++ Kodeeksempel Lineær søgning

#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

RELATEREDE ARTIKLER

Python Kodeeksempel Lineær søgning

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 mængden af ​​CPU-tid til at udføre en bestemt opgave. I den lineære søgealgoritme er opgaven at finde søgenøglen fra elementet 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øgepunktet mellem indeks 0 til n-1. I værste fald vil algoritmen forsøge at matche alle elementer fra arrayet med søgeelementet.

I så fald vil den værste kompleksitet være O(n). Her betyder "O"-big O-notation kompleksitetsfunktionen.

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

Lad os sige, at vi søger efter et element, der ligger i den første position ved 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

Rumkompleksitet 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 vil vi bytte søgeelementet med dets tidligere element i arrayet. Lad os f.eks. sige, at du har en matrix som følgende:

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

Nu vil vi søge efter 4. Transponeringstrin:

Transponering i lineær søgning

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 data [5] og data[4]. Så vil dataarrayet se sådan ud:

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

Hvis du nu bemærker, at jo hyppigere en nøgle søges i, jo mere formindsker den indekset. Dermed falder antallet af sammenligninger.

Flyt til fronten:

I denne metode bytter vi søgeelementet i det 0. indeks. For hvis der søges igen, kan vi finde det på O(1) tidspunkt.

Flyt til fronten i lineær søgning

Anvendelse af lineær søgealgoritme

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

  • For små arrays eller kun nogle 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.