Searching

Binary Search First Occurrence

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

Algorithm

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.

Basic Implementation

basic.kt
Replay: real traced execution (multi-file project)
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)
}

  1. arr ← [1, 2, 4, 4, 4, 7, 9], target ← 4, result ← -1

    1fun main() {2	val arr = intArrayOf(1, 2, 4, 4, 4, 7, 9)
    values this step[1, 2, 4, 4, 4, 7, 9]arr4target-1result

  2. hi ← 2, mid ← 3, result ← 3

    7while (lo <= hi) {8	val mid = lo + (hi - lo) / 29	if (arr[mid] == target) {
    values this step6 → 2hi3mid3result0lo

  3. lo ← 2, mid ← 1

    7while (lo <= hi) {8	val mid = lo + (hi - lo) / 29	if (arr[mid] == target) {
    values this step0 → 2lo1mid2hi3result

  4. hi ← 1, result ← 2, mid ← 2

    7while (lo <= hi) {8	val mid = lo + (hi - lo) / 29	if (arr[mid] == target) {
    values this step2 → 1hi3 → 2result2mid2lo

  5. stdout ← 2

    17	}18	println(result)19}
    values this step2stdout2result

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.