Vad är en binär sökning?

Anta att en person har ett mycket stort sortiment av föremål och ordnar dem på något ordnat sätt i en lång rad. Den individen kan snabbt ta reda på var i raden ett visst objekt finns med hjälp av en binär sökning. Denna sökning görs genom att kontrollera det mellersta objektet i raden och om det mellersta objektet inte är det sökta objektet, letar du sedan bara i en av halvorna i raden där objektet kan vara. Personen skulle veta vilken hälft att fortsätta titta på eftersom föremålen är ordnade i ordning. Dessa två steg utförs om och om igen, på mindre och mindre halvor, tills objektet antingen hittas eller det inte finns någonstans kvar att titta på.

Inom datavetenskapen är en binär sökning en steg-för-steg-procedur som hittar platsen eller indexet för ett objekt i en sekvensvis sorterad uppsättning data. Det åstadkommer detta genom att jämföra ett känt värde med ett angiven medelelement i matrisen och, om det inte är ekvivalent, begränsar upprepade gånger mittelementjämförelsen med den mindre relevanta halvan av uppsättningen tills en ekvivalens erhålls eller listan är uttömd.

En binär sökning, ibland kallad en halvintervallsökning, är mycket snabbare än en grundläggande sekventiell sökning som börjar i ena änden av en lista med objekt och jämför varje objekt på vägen tills en matchning hittas eller tills sökningen når slutet av listan. Om en person hade 100 objekt i rad och det sista objektet var det som letades efter, skulle en sekventiell sökning ta 100 jämförelser. Halveringsmetoden kräver dock endast sju jämförelser högst innan objektet hittas. Det är uppenbarligen mycket effektivare än en sekventiell sökning.

Den största nackdelen med en binär sökning är att listan med objekt måste sorteras för att denna sökning ska fungera. Att sortera en lista tar tid. Det kan ta längre tid att sortera sedan använda denna typ av sökning än att göra en annan typ av sökning i första hand.

Att kunna använda information, särskilt från mycket stora datamängder, är viktigt för att kunna utföra många uppgifter i livet. Datavetenskapens disciplin hanterar många typer av problem, inklusive att hitta effektiva sätt att söka efter information så att användbara resultat uppnås. En binär sökning är bara en av många algoritmer som är tillgängliga för sökning genom data.