Home-theater-designers
Evnen til å søke etter noen data er et viktig aspekt ved datavitenskap. Søkealgoritmer brukes til å lete etter et bestemt element i et datasett.
Algoritmer returnerer et boolsk resultat (sant eller usant) til et søk. De kan også endres for å gi den relative posisjonen til funnet verdi.
For denne artikkelen vil algoritmene konsentrere seg om å avgjøre om det finnes en verdi.
Lineære søkealgoritmer
Lineært søk er også kjent som sekvensielt søk. I denne typen søk blir hver verdi i en liste besøkt en etter en på en ryddig måte mens du sjekker om ønsket verdi eksisterer.
Algoritmen sjekker verdi etter verdi til den finner verdien du leter etter eller går tom for verdier for å søke. Når det går tom for verdier for å søke, betyr det at søket ditt ikke finnes i listen.
En sekvensiell søkealgoritme tar inn en liste med verdier og ønsket element i listen som sine parametere. Returresultatet initialiseres som Falsk og vil endre til ekte når ønsket verdi er funnet.
Se Python -implementeringen nedenfor som et eksempel:
def linearSearch(mylist, item):
found = False
index = 0
while index if mylist[index] == item:
found = True
else:
index = index+1
return found Algoritme analyse
Det beste tilfellet skjer når det ønskede elementet er det første på listen. Det verste tilfellet oppstår når ønsket element er det siste på listen (det niende elementet). Derfor er tidskompleksiteten for lineært søk O (n).
Det gjennomsnittlige case -scenariet i algoritmen ovenfor er n/2.
I slekt: Hva er Big-O Notation?
Endret lineært søk
Det er viktig å vite at algoritmen som brukes, forutsetter at den er gitt en tilfeldig liste over elementer. Det vil si at listeelementene ikke er i noen spesiell rekkefølge.
hva er den mest brukte appen
Anta at varene var i en bestemt rekkefølge, si fra minste til største. Det ville være mulig å oppnå en viss fordel i beregning.
Ta et eksempel på å lete etter 19 i den gitte listen: [2, 5, 6, 11, 15, 18, 23, 27, 34]. Etter å ha nådd 23, ville det bli klart at varen du leter etter ikke finnes i listen. Derfor vil det ikke lenger være viktig å fortsette å søke i resten av listeelementene.
Binære søkealgoritmer
Du har sett hvordan en bestilt liste kan redusere beregningen som trengs. Binær søkealgoritme drar enda mer fordel av denne effektiviteten som det å ha en ordnet liste introduserer.
Algoritmen begynner med å ta en mellomverdi av en ordnet liste og kontrollere om det er ønsket verdi. Hvis det ikke er det, kontrolleres verdien om den er mindre eller større enn ønsket verdi.
Hvis det er mindre, er det ikke nødvendig å sjekke den nedre halvdelen av listen. Ellers, hvis den er større, går den videre til den øvre halvdelen av listen.
Relatert: Hva er rekursjon og hvordan bruker du det?
Uavhengig av hvilken sublist (venstre eller høyre) som velges, vil mellomverdien igjen bli bestemt. Verdien kontrolleres igjen hvis det er den nødvendige verdien. Hvis det ikke er det, kontrolleres det om det er mindre eller større enn den forespurte verdien.
gratis videospiller for Windows 10
Denne prosessen gjentas til en verdi er funnet hvis den er der.
Python -implementeringen nedenfor er for den binære søkealgoritmen.
def binarySearch (mylist, item):
low = 0
high = len(mylist) - 1
found = False
while low <= high and not found: mid = (low + high) // 2
if mylist[mid] == item:found = True
elif item else:low = mid + 1
return found Algoritme analyse
Det beste tilfellet skjer når det ønskede elementet er funnet i midten. Det verste scenariet er imidlertid ikke like greit. Følg analysen nedenfor:
Etter den første sammenligningen vil n/2 varer bli igjen. Etter den andre vil n/4 elementer bli igjen. Etter den tredje, n/8.
Legg merke til at antallet varer fortsetter å halvere til de når n/2i hvor i er antall sammenligninger. Etter all splittelsen ender vi opp med bare 1 vare.
Dette medfører:
n/2i = 1 Derfor er binært søk O (logg n).
Gå videre til sortering
I binært søk vurderte vi et tilfelle der den gitte matrisen allerede var bestilt. Men anta at du hadde et uordnet datasett, og at du ønsket å utføre binært søk på det. Hva ville du gjort?
Svaret er enkelt: sorter det. Det er en rekke sorteringsteknikker innen informatikk som har blitt godt undersøkt. En av disse teknikkene du kan begynne å studere er utvalgssorteringsalgoritmen, mens vi har mange guider knyttet til andre områder også.
Dele Dele kvitring E -post Slik bruker du utvalgssorteringUtvalgssortering er litt vanskelig å forstå for nybegynnere, men det er ikke så utfordrende når du først får sving i tingene.
Les neste Relaterte temaer- Programmering
- Teknologi forklart
- Programmering
- Algoritmer
- Dataanalyse
Jerome er personalforfatter på MakeUseOf. Han dekker artikler om programmering og Linux. Han er også en kryptoentusiast og holder alltid oversikt over kryptoindustrien.
Mer fra Jerome DavidsonAbonner på vårt nyhetsbrev
Bli med i vårt nyhetsbrev for tekniske tips, anmeldelser, gratis ebøker og eksklusive tilbud!
Klikk her for å abonnere