BinarySearch benchmark

package benchmarks.binary_search

import org.openjdk.jmh.annotations.*
import java.util.*

@BenchmarkMode(Mode.AverageTime)
@State(Scope.Benchmark)
open class BinarySearch {
    private val max = 10_000_000
    private val largNumbers = (0..max).toList()
    private val r = Random(System.currentTimeMillis())

    @Benchmark
    fun binary_search(): Int {
        val item = r.nextInt(max)

        val r = binarySearch(largNumbers, item)

        assert(r >= 0)

        return r
    }


    @Benchmark
    fun builtin_binary_search(): Int {
        val item = r.nextInt(max)

        val r = largNumbers.binarySearch(item)

        assert(r >= 0)

        return r
    }
}



fun rangeCheck(size: Int, fromIndex: Int, toIndex: Int) {
    when {
        fromIndex > toIndex -> throw IllegalArgumentException("fromIndex ($fromIndex) is greater than toIndex ($toIndex).")
        fromIndex < 0 -> throw IndexOutOfBoundsException("fromIndex ($fromIndex) is less than zero.")
        toIndex > size -> throw IndexOutOfBoundsException("toIndex ($toIndex) is greater than size ($size).")
    }
}

fun <T : Comparable<T>> binarySearch(list: List<T?>, element: T?, fromIndex: Int = 0, toIndex: Int = list.size): Int {
    rangeCheck(list.size, fromIndex, toIndex)

    var low = fromIndex
    var high = toIndex - 1

    while (low <= high) {
        val mid = (low + high).ushr(1) // safe from overflows
        val midVal = list.get(mid)
        val cmp = when {
            midVal == element -> 0
            midVal == null -> -1
            element == null -> 1
            else -> midVal.compareTo(element)
        }

        if (cmp < 0)
            low = mid + 1
        else if (cmp > 0)
            high = mid - 1
        else
            return mid // key found
    }
    return -(low + 1)  // key not found
}