Hvad er en binær søgning?

Antag, at en person har et meget stort udvalg af genstande og arrangerer dem på en ordnet måde i en lang række. Denne person kan hurtigt finde ud af, hvor i rækken et bestemt objekt befinder sig ved hjælp af en binær søgning. Denne søgning udføres ved at kontrollere det midterste element i rækken, og hvis det midterste objekt ikke er det søgte emne, kig derefter derefter kun i en af ​​halvdelene i den række, hvor emnet kan være. Personen ville vide, hvilken halvdel han skal fortsætte med at kigge i, fordi varerne er arrangeret i rækkefølge. Disse to trin udføres igen og igen på mindre og mindre halvdele, indtil varen enten findes, eller der ikke er nogen steder tilbage at se på.

Inden for computervidenskab er en binær søgning en trin-for-trin-procedure, der finder placeringen eller indekset for et element i et sekventielt sorteret datasæt. Det opnår dette ved at sammenligne en kendt værdi med et udpeget mellemelement i arrayet og, hvis det ikke er ækvivalent, gentagne gange begrænse midtelementets sammenligning med den mindre relevante halvdel af sættet, indtil der opnås en ækvivalens eller listen er opbrugt.

En binær søgning, som undertiden kaldes en halvintervalsøgning, er meget hurtigere end en grundlæggende sekventiel søgning, der starter i den ene ende af en liste over elementer og sammenligner hvert element undervejs, indtil en match findes, eller indtil søgningen når slutningen af listen. Hvis en person havde 100 genstande i træk, og den sidste vare var den, der blev søgt efter, ville en sekventiel søgning tage 100 sammenligninger. Halveringsmetoden kræver dog kun syv sammenligninger højst, før varen findes. Det er naturligvis meget mere effektivt end en sekventiel søgning.

Den største ulempe ved en binær søgning er, at listen over emner skal sorteres for at denne søgning kan fungere. Det tager tid at sortere en liste. Det kan tage længere tid at sortere derefter bruge denne type søgning end først at foretage en anden type søgning.

At være i stand til at bruge information, især fra meget store datasæt, er vigtig for at udføre mange opgaver i livet. Computervidenskabens disciplin beskæftiger sig med mange typer problemer, herunder at finde effektive måder at søge efter information på, så man får nyttige resultater. En binær søgning er kun en af ​​mange algoritmer, der er tilgængelige til søgning gennem data.