- Mål
- Stadig mulige
- Sammenlignet
- Udelukket
- Fundet
Binær søgning
Binær søgning finder en værdi i en sorteret liste ved altid at kigge i midten. Er den midterste værdi for lille, kan den søgte værdi kun ligge efter den; er den for stor, kun før den. Uanset hvad udelukkes halvdelen af det, der er tilbage. Vælg den værdi, du vil søge efter, gå søgningen igennem trin for trin, og se det skraverede område skrumpe, indtil værdien er fundet, eller der intet er tilbage. Tryk på Afspil for at se søgningen, eller brug Trin og Tilbage for at gå ét trin ad gangen. Træk i trinskyderen for at hoppe hvorhen du vil. Den stiplede linje viser den værdi, du søger efter, og det skraverede område er, hvor den stadig kan være. Binær søgning kræver en sorteret liste, så en usorteret liste bliver sorteret først. Vælg værdien, hvor mange søjler, eller skriv dine egne tal. Når brættet er valgt, går piletasterne et trin, mellemrumstasten afspiller og sætter på pause, og Home og End hopper til starten og slutningen.
Sådan virker det
- Vælg den værdi, du vil søge efter, og hvor mange søjler. Eller skriv dine egne tal: binær søgning sorterer dem først.
- Tryk på Afspil, eller brug Trin og Tilbage for at gå ét trin ad gangen. Træk i trinskyderen for at hoppe til et vilkårligt sted i søgningen.
- Sammenlign feltet Sammenligninger med Lineær søgning ville kræve, for en værdi nær slutningen eller en, der mangler.
Sådan virker binær søgning
Hold styr på den del af den sorterede liste, der stadig kan indeholde den søgte værdi; i starten er det hele listen. Se på værdien i midten af den. Er den lig med den søgte værdi, er du færdig. Er den mindre, kan den søgte værdi kun ligge efter den, så fortsæt med delen efter midten. Er den større, så fortsæt med delen før. Når der intet er tilbage, er den søgte værdi ikke i listen.
Hvorfor den er så hurtig
Hver sammenligning halverer den del, der er tilbage. Starter du med n værdier, er der efter k sammenligninger højst omkring n/2ᵏ tilbage, så søgningen slutter efter højst ⌊log₂ n⌋ + 1 sammenligninger: 6 for 40 værdier, 10 for 1.000, 20 for en million. Lineær søgning kan blive nødt til at se på hver eneste værdi. Hagen er, at listen skal være sorteret, og at holde den sorteret, eller sortere den først, har sin egen pris.
Ofte stillede spørgsmål
Hvordan virker binær søgning?
Den sammenligner den søgte værdi med den midterste værdi i den del af en sorteret liste, der stadig kan indeholde den. Ens betyder fundet; ellers falder den halvdel væk, der ikke kan indeholde værdien, og søgningen fortsætter i den anden halvdel, indtil værdien er fundet, eller der intet er tilbage.
Hvor mange sammenligninger kræver binær søgning?
Højst ⌊log₂ n⌋ + 1 for en liste med n værdier: 6 for 40, 10 for 1.000, 20 for en million. Hver sammenligning halverer det, der er tilbage.
Hvorfor kræver binær søgning en sorteret liste?
Fordi det kun er i en sorteret liste, at én sammenligning fortæller dig, hvilken side den søgte værdi er på. I en usorteret liste siger en mindre værdi i midten intet om, hvor den søgte værdi er, så intet kan udelukkes.
Hvilken værdi finder den, når der er dubletter?
En hvilken som helst af dem, afhængigt af hvor midterpunkterne falder. Varianter, der søger videre til venstre eller højre efter et match, finder den første eller den sidste forekomst.
Bliver mine tal sendt nogen steder hen?
Nej. Søgningen kører i din browser, og dine seneste indstillinger bliver i denne browsers lokale lager.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Gå til Editor