{"id":91769,"date":"2022-10-12T05:01:41","date_gmt":"2022-10-12T10:01:41","guid":{"rendered":"https:\/\/blogging-techies.com\/sw\/linjara-och-binara-sokalgoritmer-forklaras\/"},"modified":"2022-10-12T05:01:41","modified_gmt":"2022-10-12T10:01:41","slug":"linjara-och-binara-sokalgoritmer-forklaras","status":"publish","type":"post","link":"https:\/\/blogging-techies.com\/sw\/linjara-och-binara-sokalgoritmer-forklaras\/","title":{"rendered":"Linj\u00e4ra och bin\u00e4ra s\u00f6kalgoritmer f\u00f6rklaras"},"content":{"rendered":"
\n

M\u00f6jligheten att s\u00f6ka efter vissa data \u00e4r en viktig aspekt av datavetenskap. S\u00f6kalgoritmer anv\u00e4nds f\u00f6r att leta efter ett visst objekt i en datam\u00e4ngd.<\/p>\n

Algoritmer returnerar ett booleskt resultat (sant eller falskt) till en s\u00f6kfr\u00e5ga. De kan ocks\u00e5 modifieras f\u00f6r att ge den relativa positionen f\u00f6r det hittade v\u00e4rdet.<\/p>\n

F\u00f6r den h\u00e4r artikeln kommer algoritmerna att koncentrera sig p\u00e5 att avg\u00f6ra om ett v\u00e4rde finns.<\/p>\n

<\/span> Linj\u00e4ra s\u00f6kalgoritmer<\/span><\/h2>\n

Linj\u00e4r s\u00f6kning kallas \u00e4ven sekventiell s\u00f6kning. I denna typ av s\u00f6kning bes\u00f6ks varje v\u00e4rde i en lista ett efter ett p\u00e5 ett ordnat s\u00e4tt samtidigt som man kontrollerar om det \u00f6nskade v\u00e4rdet finns.<\/p>\n

Algoritmen kontrollerar v\u00e4rde f\u00f6r v\u00e4rde tills den hittar v\u00e4rdet du letar efter eller tar slut p\u00e5 v\u00e4rden att s\u00f6ka efter. N\u00e4r det tar slut p\u00e5 v\u00e4rden att s\u00f6ka betyder det att din s\u00f6kfr\u00e5ga inte finns i listan.<\/p>\n

En sekventiell s\u00f6kalgoritm tar in en lista med v\u00e4rden och det \u00f6nskade objektet i listan som sina parametrar. Returresultatet initieras som Falsk<\/strong> och kommer att \u00e4ndras till Sann<\/strong> n\u00e4r \u00f6nskat v\u00e4rde hittas.<\/p>\n

Se Python-implementeringen nedan som ett exempel:<\/p>\n

def linearSearch(mylist, item):found = Falseindex = 0while index < len(mylist) and not found:if mylist[index] == item:found = Trueelse:index = index+1return found<\/pre>\n
<\/span>Algoritmanalys<\/span><\/h3>\n
Det b\u00e4sta scenariot intr\u00e4ffar n\u00e4r det \u00f6nskade objektet \u00e4r det f\u00f6rsta p\u00e5 listan.  Det v\u00e4rsta fallet intr\u00e4ffar n\u00e4r den \u00f6nskade posten \u00e4r den sista p\u00e5 listan (den n:e posten).  D\u00e4rf\u00f6r \u00e4r tidskomplexiteten f\u00f6r linj\u00e4r s\u00f6kning O(n).<\/p>\n
Det genomsnittliga fallscenariot i ovanst\u00e5ende algoritm \u00e4r n\/2.<\/p>\n
<\/span>Modifierad linj\u00e4r s\u00f6kning<\/span><\/h3>\n
Det \u00e4r viktigt att veta att algoritmen som anv\u00e4nds f\u00f6ruts\u00e4tter att en slumpm\u00e4ssig lista med objekt tillhandah\u00e5lls till den.  Det vill s\u00e4ga att listobjekten inte \u00e4r i n\u00e5gon speciell ordning.<\/p>\n
Anta att f\u00f6rem\u00e5len var i en viss ordning, s\u00e4g fr\u00e5n minsta till st\u00f6rsta.  Det skulle vara m\u00f6jligt att uppn\u00e5 en viss f\u00f6rdel i ber\u00e4kningen.<\/p>\n
Ta ett exempel p\u00e5 att leta efter 19 i den givna listan: [2, 5, 6, 11, 15, 18, 23, 27, 34].  Efter att ha n\u00e5tt 23 skulle det st\u00e5 klart att objektet som letas efter inte finns i listan.  D\u00e4rf\u00f6r skulle det inte l\u00e4ngre vara viktigt att forts\u00e4tta s\u00f6ka i resten av listobjekten.<\/p>\n
<\/span>  Bin\u00e4ra s\u00f6kalgoritmer<\/span><\/h2>\n
Du har sett hur en ordnad lista kan minska ber\u00e4kningen som beh\u00f6vs.  Bin\u00e4r s\u00f6kalgoritm drar \u00e4nnu mer f\u00f6rdel av denna effektivitet som en ordnad lista introducerar.<\/p>\n
Algoritmen b\u00f6rjar med att ta ett mellanv\u00e4rde av en ordnad lista och kontrollera om det \u00e4r det \u00f6nskade v\u00e4rdet.  Om det inte \u00e4r det, kontrolleras v\u00e4rdet om det \u00e4r mindre eller st\u00f6rre \u00e4n det \u00f6nskade v\u00e4rdet.<\/p>\n
Om det \u00e4r mindre beh\u00f6ver du inte kontrollera den nedre halvan av listan.  Annars, om den \u00e4r st\u00f6rre, flyttar den vidare till den \u00f6vre halvan av listan.<\/p>\n
Oavsett vilken underlista (v\u00e4nster eller h\u00f6ger) som v\u00e4ljs, kommer mittv\u00e4rdet \u00e5ter att fastst\u00e4llas.  V\u00e4rdet kontrolleras igen om det \u00e4r det \u00f6nskade v\u00e4rdet.  Om det inte \u00e4r det kontrolleras det om det \u00e4r mindre eller st\u00f6rre \u00e4n det beg\u00e4rda v\u00e4rdet.<\/p>\n
Denna process upprepas tills ett v\u00e4rde hittas om det finns d\u00e4r.<\/p>\n
Python-implementeringen nedan \u00e4r f\u00f6r den bin\u00e4ra s\u00f6kalgoritmen.<\/p>\n
def binarySearch(mylist, item):<\/p>\n
low = 0 high = len(mylist) - 1 found = False while low <= high and not found: mid = (low + high) \/\/ 2 if mylist[mid] == item:found = Trueelif item < mylist[mid]:high = mid - 1 else:low = mid + 1return found<\/pre>\n
<\/span>Algoritmanalys<\/span><\/h3>\n
Det b\u00e4sta scenariot intr\u00e4ffar n\u00e4r det \u00f6nskade objektet visar sig vara mittobjektet.  Det v\u00e4rsta scenariot \u00e4r dock inte lika enkelt.  F\u00f6lj analysen nedan:<\/p>\n
Efter den f\u00f6rsta j\u00e4mf\u00f6relsen kommer n\/2 objekt att finnas kvar.  Efter den andra kommer n\/4 objekt att finnas kvar.  Efter den tredje, n\/8.<\/p>\n
L\u00e4gg m\u00e4rke till att antalet objekt forts\u00e4tter att halveras tills de n\u00e5r n\/2i d\u00e4r i \u00e4r antalet j\u00e4mf\u00f6relser.  Efter all splittring slutar vi med endast 1 objekt.<\/p>\n
Detta medf\u00f6r:<\/p>\n
n\/2i=1 D\u00e4rf\u00f6r \u00e4r bin\u00e4r s\u00f6kning O(log n).<\/p>\n
<\/span>  G\u00e5r vidare till sortering<\/span><\/h2>\n
I bin\u00e4r s\u00f6kning \u00f6verv\u00e4gde vi ett fall d\u00e4r den givna arrayen redan var best\u00e4lld.  Men anta att du hade en oordnad dataupps\u00e4ttning och du ville utf\u00f6ra bin\u00e4r s\u00f6kning p\u00e5 den.  Vad skulle du g\u00f6ra?<\/p>\n
Svaret \u00e4r enkelt: sortera det.  Det finns ett antal sorteringstekniker inom datavetenskap som har unders\u00f6kts v\u00e4l.  En av dessa tekniker du kan b\u00f6rja studera \u00e4r urvalssorteringsalgoritmen, medan vi har massor av guider relaterade till andra omr\u00e5den ocks\u00e5.<\/p>\n
    Om f\u00f6rfattaren<\/strong><\/p>\n
            Jerome Davidson (33 artiklar publicerade)
<\/strong><\/p>\n
Jerome \u00e4r personalskribent p\u00e5 MakeUseOf.  Han t\u00e4cker artiklar om programmering och Linux.  Han \u00e4r ocks\u00e5 en kryptoentusiast och h\u00e5ller alltid koll p\u00e5 kryptoindustrin.<\/p>\n
                            Mer fr\u00e5n Jerome Davidson<\/p>\n
<\/span>Prenumerera p\u00e5 v\u00e5rt nyhetsbrev<\/span><\/h4>\n
G\u00e5 med i v\u00e5rt nyhetsbrev f\u00f6r tekniska tips, recensioner, free e-b\u00f6cker och exklusiva erbjudanden!<\/p>\n
Klicka h\u00e4r f\u00f6r att prenumerera<\/p>\n<\/p><\/div>\n  
\n
\n
Table of Contents<\/p>\nToggle<\/span><\/path><\/svg><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n