Binary Search First Occurrence

Find the first copy of a duplicated target by recording matches and continuing to search the left half.

Algorithm

Basic Implementation

basic.kt

fun main() {
	val arr = intArrayOf(1, 2, 4, 4, 4, 7, 9)
	val target = 4
	var lo = 0
	var hi = arr.size - 1
	var result = -1
	while (lo <= hi) {
		val mid = lo + (hi - lo) / 2
		if (arr[mid] == target) {
			result = mid
			hi = mid - 1
		} else if (arr[mid] < target) {
			lo = mid + 1
		} else {
			hi = mid - 1
		}
	}
	println(result)
}

Complexity

Time: O(log n)
Space: O(1)

Implementation notes

Kotlin stores the sorted input as a primitive IntArray, and arr is a val reference because the search only reads indexed Int values.
target is a val Int; lo, hi, and result are mutable var Int scalars that carry the search window and first-match sentinel.
result starts at -1, so a miss would print -1 without needing nullable Int? state.
The loop guard is while (lo <= hi). The midpoint uses lo + (hi - lo) / 2, keeping all index math in Int.
On arr[mid] == target, the code records result = mid and moves hi = mid - 1 to keep searching for an earlier duplicate.
On arr[mid] < target, lo = mid + 1; otherwise hi = mid - 1. All branches compare primitive Int values.
The trace records mid=3 with result 3 and hi=2, then mid=1 moving lo to 2, then mid=2 updating result to the first occurrence 2.
println(result) prints the final index as 2.

execution replay The checked-in replay follows the language-neutral state table for `search-binary-first`.

cross-language comparison This Kotlin DSA version keeps the same data and final output as every other DSA book in this wave.