Binary Search (sång)

Hej, alla kreativa!

Jag skrev en liten låt i går om binära sökalgoritmer.
Det kan låta nördigt och det är det också.

Här är den: https://www.almnil.se/music/binary-search.flac


För er som inte vet vad en binär sökalgoritm (binary search algorithm) är:

Det är användbart när man programmerar.
Om man ska hitta något i en ordnad lista, till exempel hitta nummer 12 i den här listan:

1 2 3 5 6 7 9 10 11 12 15 19 20 500 501

Så kan man börja titta i mitten och se om talet man söker är större eller mindre.
Beroende på vilket det är gör man sedan om samma sökning på den högra eller vänstra halvan.
Till exempel, för att hitta 12, börjar vi i mitten, alltså på 10.
12 är större, så vi tittar i mitten av den högra halvan, på 19.
12 är mindre, så vi tittar på vänstra halvan av halvan vi redan är på, på 12.
Då hittade vi det vi sökte i en lista med 15 tal genom att bara titta på tre tal.

Det maximala antalet tal man behöver titta på är lika med bas-2-logaritmen av antalet tal i listan.
Det betyder att om vi har en lista med en miljard tal så behöver vi aldrig titta på mer än 30 av dem.
Mycket användbart!