Möjligheten att söka efter vissa data är en viktig aspekt av datavetenskap. Sökalgoritmer används för att leta efter ett visst objekt i en datamängd.
Algoritmer returnerar ett booleskt resultat (sant eller falskt) till en sökfråga. De kan också modifieras för att ge den relativa positionen för det hittade värdet.
För den här artikeln kommer algoritmerna att koncentrera sig på att avgöra om ett värde finns.
Linjära sökalgoritmer
Linjär sökning kallas även sekventiell sökning. I denna typ av sökning besöks varje värde i en lista ett efter ett på ett ordnat sätt samtidigt som man kontrollerar om det önskade värdet finns.
Algoritmen kontrollerar värde för värde tills den hittar värdet du letar efter eller tar slut på värden att söka efter. När det tar slut på värden att söka betyder det att din sökfråga inte finns i listan.
En sekventiell sökalgoritm tar in en lista med värden och det önskade objektet i listan som sina parametrar. Returresultatet initieras som Falsk och kommer att ändras till Sann när önskat värde hittas.
Se Python-implementeringen nedan som ett exempel:
def linearSearch(mylist, item):
found = False
index = 0
while index < len(mylist) and not found:
if mylist[index] == item:
found = True
else:
index = index+1
return found
Algoritmanalys
Det bästa scenariot inträffar när det önskade objektet är det första på listan. Det värsta fallet inträffar när den önskade posten är den sista på listan (den n:e posten). Därför är tidskomplexiteten för linjär sökning O(n).
Det genomsnittliga fallscenariot i ovanstående algoritm är n/2.
Modifierad linjär sökning
Det är viktigt att veta att algoritmen som används förutsätter att en slumpmässig lista med objekt tillhandahålls till den. Det vill säga att listobjekten inte är i någon speciell ordning.
Anta att föremålen var i en viss ordning, säg från minsta till största. Det skulle vara möjligt att uppnå en viss fördel i beräkningen.
Ta ett exempel på att leta efter 19 i den givna listan: [2, 5, 6, 11, 15, 18, 23, 27, 34]. Efter att ha nått 23 skulle det stå klart att objektet som letas efter inte finns i listan. Därför skulle det inte längre vara viktigt att fortsätta söka i resten av listobjekten.
Binära sökalgoritmer
Du har sett hur en ordnad lista kan minska beräkningen som behövs. Binär sökalgoritm drar ännu mer fördel av denna effektivitet som en ordnad lista introducerar.
Algoritmen börjar med att ta ett mellanvärde av en ordnad lista och kontrollera om det är det önskade värdet. Om det inte är det, kontrolleras värdet om det är mindre eller större än det önskade värdet.
Om det är mindre behöver du inte kontrollera den nedre halvan av listan. Annars, om den är större, flyttar den vidare till den övre halvan av listan.
Oavsett vilken underlista (vänster eller höger) som väljs, kommer mittvärdet åter att fastställas. Värdet kontrolleras igen om det är det önskade värdet. Om det inte är det kontrolleras det om det är mindre eller större än det begärda värdet.
Denna process upprepas tills ett värde hittas om det finns där.
Python-implementeringen nedan är för den binära sökalgoritmen.
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 < mylist[mid]:high = mid - 1
else:low = mid + 1
return found
Algoritmanalys
Det bästa scenariot inträffar när det önskade objektet visar sig vara mittobjektet. Det värsta scenariot är dock inte lika enkelt. Följ analysen nedan:
Efter den första jämförelsen kommer n/2 objekt att finnas kvar. Efter den andra kommer n/4 objekt att finnas kvar. Efter den tredje, n/8.
Lägg märke till att antalet objekt fortsätter att halveras tills de når n/2i där i är antalet jämförelser. Efter all splittring slutar vi med endast 1 objekt.
Detta medför:
n/2i=1 Därför är binär sökning O(log n).
Går vidare till sortering
I binär sökning övervägde vi ett fall där den givna arrayen redan var beställd. Men anta att du hade en oordnad datauppsättning och du ville utföra binär sökning på den. Vad skulle du göra?
Svaret är enkelt: sortera det. Det finns ett antal sorteringstekniker inom datavetenskap som har undersökts väl. En av dessa tekniker du kan börja studera är urvalssorteringsalgoritmen, medan vi har massor av guider relaterade till andra områden också.
Om författaren
Jerome Davidson (33 artiklar publicerade)
Jerome är personalskribent på MakeUseOf. Han täcker artiklar om programmering och Linux. Han är också en kryptoentusiast och håller alltid koll på kryptoindustrin.
Mer från Jerome Davidson
Prenumerera på vårt nyhetsbrev
Gå med i vårt nyhetsbrev för tekniska tips, recensioner, free e-böcker och exklusiva erbjudanden!
Klicka här för att prenumerera
