Binary Search (Iterative & Recursive)

Keep one interval convention throughout

Binary search requires sorted input and an invariant locating every possible match inside the current interval. This version uses a half-open interval [low, high).

Copy codefun binarySearch(values: IntArray, target: Int): Int {
    var low = 0
    var high = values.size
    while (low < high) {
        val middle = low + (high - low) / 2
        when {
            values[middle] < target -> low = middle + 1
            values[middle] > target -> high = middle
            else -> return middle
        }
    }
    return -1
}

Every non-returning branch strictly shrinks the interval. With duplicates, this returns some matching index, not necessarily the first. The midpoint formula avoids overflow from adding two large indexes directly.

Exercise

Trace searches in empty, one-element, and two-element arrays. Test missing values before and after the range. Write a recursive version with the same half-open invariant and compare results against a linear scan.

Check: do not mix an inclusive upper bound with a half-open termination condition; that is a common source of skipped matches and infinite loops.

Further reading: Binary search