bin-search.scala

// size = (1 << 25),        time = 800 ms
// size = (1 << 25) - 1999, time = 400 ms ???
// size = (1 << 24),        time = 700 ms

val size = 1 << 25

val randos = new util.Random()

val arr = Array.fill(size)(randos.nextInt)
java.util.Arrays.sort(arr)

val queries = Array.fill(1 << 20)(randos.nextInt)

val s = System.nanoTime
var sum = 0

var i = 0; while (i < queries.length) {
  sum += java.util.Arrays.binarySearch(arr, queries(i))
  i += 1
}

println((System.nanoTime - s)/1e6+" ms")
println(sum)