Binary Interval Search

BinaryIntervalSearch.kt

class BinaryIntervalSearch(
    private val initialValue: Int,
    private val estimationStep: Int,
    private val maxValue: Int,
    val meetsCondition: () -> Boolean = { true }
) {

    fun search(doWork: (newValue: Int) -> Unit): Int {
        if (this.maxValue < initialValue) {
            throw Error("Max value cant be smaller than initial value")
        }

        if (this.estimationStep > maxValue - initialValue) {
            throw Error("Step cant be larger than range")
        }

        val limits = findInitialLimit(doWork)
        return searchInsideInterval(limits, doWork)
    }

    private fun searchInsideInterval(limits: Pair<Int, Int>, doWork: (newValue: Int) -> Unit): Int {
        var left = limits.first
        var right = limits.second

        while (right - left > 1) {
            val middle = left + (right - left) / 2
            doWork(middle)

            if (meetsCondition()) {
                left = middle
            } else {
                right = middle
            }
        }

        return left
    }

    /** Guess right upper value by adding step to current value and prevent left 0 or positive value */
    private fun findInitialLimit(doWork: (newValue: Int) -> Unit): Pair<Int, Int> {
        var current = initialValue
        doWork(current)

        while (this.meetsCondition() && current <= this.maxValue) {
            current += this.estimationStep
            doWork(current)
        }

        var leftLimit = current - this.estimationStep
        leftLimit = if (leftLimit < this.initialValue) { this.initialValue } else { leftLimit }
        val rightLimit = if (current > this.maxValue) { this.maxValue } else { current }

        return Pair(leftLimit, rightLimit)
    }

}

https://en.wikipedia.org/wiki/Binary_search_algorithm