Grunnleggende Programmering

39 - Lineært og binært søk i tabeller


Her går jeg igjennom lineært og binært søk i tabeller. Lineært søk brukes henholdsvis for å søke i usorterte tabeller, mens binært søk brukes i sorterte tabeller.

Besøk UDL på:

Om du kunne tenkt deg å hjelpe meg med å dekke kostnadene rundt UDL, så hadde jeg vært VELDIG takknemlig! En liten donasjon går en lang vei.

Kommentarer

Logg inn hvis du ønsker å legge igjen en kommentar!
Anonym 2012-12-12

Hva er fordelen ved å sortere først og så søke?

colsen91 2012-12-12

La oss si at du har en tabell med n elementer. Dersom tabellen er usortert vil valg av søkemetode være likegyldig da en ikke kan forutsi på noen måte hvor det elementet en leter etter ligger. Altså vil en risikere å sammenligne n elementer før en finner det en leter etter, og hvis n = 1 000 000, sier det seg selv at dette er noe ugunstig. Dog, om tabellen er sortert kan en bruke for eksempel binærsøk til å minske antall sammenlikninger betraktelig. Dette skjer ved at først sjekker søket elementet som ligger i midten av tabellen og finner ut om elementet du leter etter er større eller mindre enn dette elementet. Om elementet er mindre, fortsetter søket på samme vis i venstre del av tabellen, og om elementet er større fortsetter søket på samme vis i høyre del av tabellen. På denne måten kan en sortert tabell på 1 000 000 elementer søkes igjennom og finne et hvilket som helst element på (maksimum) 13 sammenlikninger, isteden for (maksimum) 1 000 000 sammenlikninger. Det er alikevel et lite "men" inne i bildet her, og det er det at å sortere en tabell i seg selv krever ganske mye datakraft, så hvis en bare skal foreta et par enkeltsøk vil det lønne seg å søke linært, men om tabellen skal gjennomgå flere søk, vil det lønne seg å sortere den først. Altså, kort oppsummert krever det langt mindre datakraft å søke i en tabell som er sortert. Håper dette ga litt forklaring :) Christer

Anonym 2012-12-12

Takk for rask respons, jeg ser problemstillingen med datamengde. Det finnes sikkert en graf over når det lønner seg å sortere først.

colsen91 2012-12-13

Ikke noe problem :) Og ja det gjør det sikkert, dog det er heller ikke noe problem å regne seg fram til dette. Da sortering typisk bruker n*log(n) operasjoner, og binærsøk bruker log(n) sammenlikninger for å søke igjennom en tabell. Kort sagt kan en si at dersom du skal søke igjennom tabellen færre ganger enn antall operasjoner et binærsøk ville brukt på å søke igjennom tabellen, er det ingen vits å sortere på forhånd (hvis dette var forståelig :)). Christer

Besøk UDL på:

Om du kunne tenkt deg å hjelpe meg med å dekke kostnadene rundt UDL, så hadde jeg vært VELDIG takknemlig! En liten donasjon går en lang vei.