Linjära och binära sökalgoritmer förklarade

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 är också känd som 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 medan man kontrollerar om det önskade värdet finns.

Algoritmen kontrollerar värde för värde tills den hittar det värde du letar efter eller tar slut på värden för sökning. När det är slut på värden för sökning 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 dess parametrar. Returresultatet initieras som Falsk och kommer att ändra till Sann när önskat värde hittas.

Se Python -implementeringen nedan som ett exempel:

def linearSearch (mylist, item):

hittat = falskt

index = 0

medan index

om mylist [index] == objekt:

found = True

annan:

index = index+1

återkomst hittad

Algoritmanalys

Det bästa fallet uppstår när det önskade objektet är det första i listan. Det värsta fallet inträffar när det önskade objektet är det sista på listan (n: e posten). Därför är tidskomplexiteten för linjär sökning O (n).

Det genomsnittliga fallscenariot i algoritmen ovan är n/2.

Relaterad: Vad är Big-O Notation?

Modifierad linjär sökning

Det är viktigt att veta att den algoritm som används antar att en slumpmässig lista med objekt tillhandahålls till den. Det vill säga att listobjekten inte är i någon särskild ordning.

Antag att artiklarna var i en viss ordning, säg från minsta till största. Det skulle vara möjligt att uppnå en viss fördel inom beräkning.

Ta ett exempel på att leta efter 19 i listan: [2, 5, 6, 11, 15, 18, 23, 27, 34]. Efter att ha nått 23 skulle det bli uppenbart 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 större nytta av denna effektivitet som en ordnad lista introducerar.

Algoritmen börjar med att ta ett medelvärde på en ordnad lista och kontrollera om det är önskat värde. 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 det är större, går det vidare till den övre halvan av listan.

Relaterad: Vad är rekursion och hur använder du det?

Oavsett vilken underlista (vänster eller höger) som väljs, bestäms mittvärdet igen. 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):

låg = 0

hög = len (mylist) - 1

hittat = falskt

medan låg <= hög och inte hittad:

mitten = (låg + hög) // 2

om mylist [mid] == objekt:

found = True

elif item

hög = mitten - 1

annan:

låg = mitten + 1

återkomst hittad

Algoritmanalys

Det bästa fallet uppstår när det önskade objektet visar sig vara det mellersta objektet. 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 vara kvar. Efter det andra kommer n/4 objekt att vara kvar. Efter den tredje, n/8.

Lägg märke till att antalet artiklar fortsätter att halvera tills de når n/2i där i är antalet jämförelser. Efter all splittring hamnar vi på endast 1 vara.

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 angivna matrisen redan var beställd. Men anta att du hade en oordnad datamängd 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 många guider relaterade till andra områden också.

Hur man använder urvalssortering

Urvalssortiment är lite knepigt att förstå för nybörjare, men det är inte för utmanande när du väl får svängarna.

Läs Nästa

Om författaren