Lineært søk: Python, C++ Eksempel
Sarah Chen
Hva er søkealgoritme?
En søkealgoritme er designet for å finne et element eller objekt fra en samling av elementer eller objekter med en gitt datastruktur. Søk for eksempel minimumshøyden fra en gitt en liste over høyder, eller søk etter den høyeste markeringen fra en liste eller rekke tall. Noen få populære søkealgoritmer inkluderer "Lineært søk", "Binært søk", "Hoppsøk", "Fibonacci-søk" osv.
Hva er lineært søk?
Lineært søk er en av de enkleste søkealgoritmene. Fra en gitt liste eller matrise søker den etter det gitte elementet en etter en. Lineært søk itererer over hele listen og sjekker om et bestemt element er lik søkeelementet. Det kalles også sekvensielt søk.
Hva gjør lineær søkefunksjon?
En matrise med heltall er gitt som "Numbers," og en variabel "element" inneholder heltall som skal søkes.
Nå kan den lineære søkealgoritmen gi følgende utdata:
- "-1"; dette betyr at det gitte elementet ikke finnes i matrisen
- Et hvilket som helst tall mellom 0 til n-1; betyr at søkeelementet er funnet, og det returnerer indeksen til elementet på matrisen. Her representerer "n" størrelsen på matrisen.
Hvordan fungerer lineært søk?
La oss si en matrise som inneholder heltall. Oppgaven er å finne et gitt tall i matrisen.
- Hvis tallet er plassert i matrisen, må vi returnere indeksen til det tallet.
- Hvis det gitte tallet ikke blir funnet, vil det returnere -1.
I flytskjemaet er "Data" heltallsmatrisen, "N" er størrelsen på matrisen, og "elementet" er nummeret vi ønsker å søke i matrisen.
Flytskjema for lineær søkealgoritme:
Her er trinnene i flytskjemaet:
Trinn 1) Les søkeelementet, "element".
Trinn 2) Start i=0 og indeks=-1
Trinn 3) Hvis jeg
Trinn 4) Hvis Data[i] er lik "element", så gå til trinn 5. Ellers gå til trinn 6.
Trinn 5) Indeks = i (Som gjenstanden finnes ved indeks nr. i). Gå til trinn 8.
Trinn 6) i = i +1.
Trinn 7) Gå til trinn 3.
Trinn 8) Stopp.
For enkelhets skyld gir vi et eksempel med en rekke heltall. Lineært søk kan også brukes i strengen, en rekke objekter eller strukturen.
Pseudokode for sekvensiell søkealgoritme
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ært søk
#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;
}
}
Utgang:
Enter a number to search: -10 -10 is found at index 14
Python Kodeeksempel Lineært søk
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))
Utgang:
Enter a number to search: -10 -10 is found at index 14
Kompleksitetsanalyse av lineær søkealgoritme
Generelt betyr tidskompleksitet mengden CPU-tid for å utføre en bestemt oppgave. I den lineære søkealgoritmen er oppgaven å finne søkenøkkelen fra elementet i matrisen.
Tre typer tidskompleksiteter er:
- I verste fall
- Best Case Scenario
- Gjennomsnittlig saksscenario
Tidskompleksiteten til lineært søk i verste tilfellesscenario:
La oss si at vi må utføre et lineært søk i en matrise med størrelsen "n". Vi kan finne søkeelementet mellom indeks 0 til n-1. I verste fall vil algoritmen prøve å matche alle elementene fra arrayet med søkeelementet.
I så fall vil verstefallskompleksiteten være O(n). Her betyr "O"-big O-notasjon kompleksitetsfunksjonen.
Tidskompleksiteten til lineært søk i best-case scenario:
La oss si at vi søker etter et element som ligger i den første posisjonen i matrisen. I dette scenariet vil ikke den lineære søkealgoritmen søke etter alle n elementene i matrisen. Så kompleksiteten vil være O(1). Dette betyr konstant tid.
Tidskompleksitet for lineært søk i gjennomsnittlig case-scenario:
Når et element er funnet ved den midterste indeksen av matrisen, kan det sies at den gjennomsnittlige kasuskompleksiteten for lineært søk er O(N), der N betyr lengden på matrisen.
Romkompleksiteten til den lineære søkealgoritmen
Plasskompleksitet for det lineære søket er alltid O(N) fordi vi ikke trenger å lagre eller bruke noen form for midlertidig variabel i den lineære søkefunksjonen.
Hvordan forbedre lineær søkealgoritme
Søk kan gjøres flere ganger gjennom programmets livssyklus. Det er også mulig at vi kjører den lineære søkealgoritmen og søker etter en bestemt nøkkel flere ganger. Vi kan bruke "Binær søkealgoritme” hvis matrisen er en sortert matrise.
Anta at matrisen består av 10 tusen tall, og målelementet er funnet ved indeksen 5000. Så, algoritmen vil prøve å sammenligne 5000 elementer. Nå er sammenligninger CPU-tunge oppgaver. For å optimalisere den lineære søkealgoritmen har vi to alternativer.
- Innarbeiding
- Flytt til foran
Transponering:
I denne metoden vil vi bytte søkeelementet med dets forrige element i matrisen. La oss for eksempel si at du har en matrise som følgende:
Data[] = {1,5,9,8,7,3,4,11}
Nå ønsker vi å søke etter 4. Transponeringstrinn:
Trinn 1) "4" er funnet i indeks 6. Det tok seks sammenligninger.
Trinn 2) Bytt data[6] og data[5]. Da vil datamatrisen se slik ut:
Data[] = {1,5,9,8,7,4,3,11}
Trinn 3) Søk 4 igjen. Funnet på indeks 5. Denne gangen tok det fem sammenligninger.
Trinn 4) Bytt data [5] og data[4]. Da vil datamatrisen se slik ut:
Data [] = {1,5,9,8,4,7,3,11}
Nå, hvis du legger merke til, jo oftere en nøkkel blir søkt, jo mer reduserer den indeksen. Dermed reduseres antallet sammenligninger.
Flytt til fronten:
I denne metoden bytter vi søkeelementet i den 0. indeksen. For hvis det søkes på nytt, kan vi finne det på O(1) tid.
Anvendelse av lineær søkealgoritme
Her er noen lineære søkeapplikasjoner vi kan bruke.
- For små matriser eller bare noen få elementer i listen, er det enklere å bruke lineært søk.
- Lineær søkemetode kan brukes i enkelt eller flerdimensjonale arrays eller andre datastrukturer.
- Vanligvis er lineært søk enkelt og effektivt for å utføre et søk i "uordnede" data. Vi kan enkelt hente en enkelt data fra den gitte uordnede listen.
