Intervalsøgning algoritme

Intervalsøgning — bedre kendt som binær søgning — finder en værdi i sorterede data ved hele tiden at halvere det område, der skal gennemsøges. Den kigger i midten, afgør om den søgte værdi ligger over eller under, og kasserer den halvdel, der ikke kan indeholde svaret. Sådan fortsætter den, indtil værdien er fundet.

Forudsætningen er, at dataene er sorterede. Er de ikke det, virker metoden ikke.

Hvorfor den er så hurtig

Forskellen på binær søgning og det åbenlyse alternativ — at gå rækken igennem fra start (sekventiel søgning) — vokser eksplosivt med mængden af data:

• 1.000 elementer: cirka 10 opslag mod op til 1.000.
• 1.000.000 elementer: cirka 20 opslag mod op til 1.000.000.

Hver gang datamængden fordobles, koster binær søgning kun ét opslag mere. Det er forskellen på øjeblikkeligt og uoverskueligt, når mængderne bliver store.

Hvor du møder den

Du bruger den hver gang du slår noget op i en database med et indeks, finder et opslag i en sorteret liste eller lader et system afgøre, hvilket interval en værdi falder i — for eksempel hvilket pristrin en mængde rammer. Den er et af de mest grundlæggende byggesten i hurtig datahåndtering, netop fordi den klarer enorme datasæt med en håndfuld sammenligninger.