Binärsökning
Wikipedia
Binärsökning är en algoritm för att avgöra om en mängd innehållet ett givet element. Sökningen utförs i flera steg och i varje steg skall man utesluta att halva den kvarvarande mängden innhåller elementet och därmed kunna koncentrera sig på den andra halvan. Detta innbär att algoritmen terminerar efter maximalt log2(n), där n betecknar storleken på mängden.
En bra liknelse kan vara att leta efter ett namnet x i en telefonkatalog. Vi börjar med att slå upp mitten av telefonkatalogen. Nu har vi tre möjliga fall, x ligger före namnen på denna sida i bokstavsordning, x ligger efter namnen på denna sida i bokstavsordning eller x ligger på denna sida (eller borde ligga). I det sistnämda fallet är det uppenbart vad man skall göra (avgör om x finns på sidan och kanske ringa honom i så fall). I det första fallet skulle vi kunna riva loss den andra halvan av katalogen (eftersom x inte kan finnas där) och sedan slå upp mitten av den halvan vi har kvar och börja om proceduren, i det andra fallet gör vi såklart samma sak fast med ombytta halvor.
I båda fallen där vi inte hittar x så slutar vi med ett problem som är hälften så stort som innan. Om telefonkatalogen är 1000 sidor så behöver vi fortfarande bara riva den 10 gånger om vi har maximal otur. Om telefonkatalogen har en miljon sidor behöver vi ändå bara riva den maximalt 20 gånger.
"Telefonkatalogen" kan självklart vara vilken sorterad lista som helst och algoritmen går således att tillämpa enbart på mängder av element som går att strikt ordna.
Ett annat enkelt sätt att tänka sig mängden är ett binärt sökträd där varje nod i trädet har maximalt två barn det ena måste vara större än och det andra mindre än nodens egna element.
