Primerjava iskanja z razpolavljanjem in interpolacijskega iskanja

Recimo, da želimo v urejeni tabeli z n elementi poiskati nek element. To lahko storimo tako, da se z zanko sprehodimo čez tabelo in poiščemo element. Vendar je to pri velikih tabelah zelo počasno (v času O(n)). Lahko pa uporabimo algoritem za iskanje z razpolavljanjem (Binary search), ki poišče željeni element veliko hitreje (v času O(log n)). Druga opcija je, da uporabimo algoritem za interpolacijsko iskanje (Interpolation search). V tej nalogi sem primerjal algoritem Binary search (funkcija binarySearch) in algoritem Interpolation search (funkcija interpolationSearch). Podroben opis problema, rešitev in rezultati testa so predstavljeni v datoteki Primerjava iskanja z razpolavljanjem in interpolacijskega iskanja.pdf. Java program, navodila za poganjanje programa, podatki in rezultati testa se nahajajo v datoteki Primerjava iskanja z razpolavljanjem in interpolacijskega iskanja.zip.