Interpolation search

[o1m2a3r4]

fun search(list: List, x: Long): Int {
var low = 0
var high = list.size - 1

while ((list[low] < x) &amp;&amp; (x < list[high]))
{
    var mid = (low + ((x - list[low])*(high - low))/(list[high] - list[low])).toInt()

    if (list[mid] < x)
    low = mid + 1
    else if (list[mid] > x)
    high = mid - 1
    else
    return mid
}

if (list[low] == x.toInt())
return low
if (list[high] == x.toInt())
return high
return -1

}

var items = listOf(2, 3, 5, 7, 11, 13, 17)

println(search(items, 1))
//print -1
println(search(items, 7))
//print 3
println(search(items, 19))
//print -1

// *** simplified speed test ***

items = Array(1000000, {0}).mapIndexed { i, _ -> i }
val count = 100

val start = Date()

for (i in 0..count-1) {
search(items, 777777)
}

val milliseconds = Date().time - start.time

println(milliseconds)
// about 4 milliseconds