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.scala

object Main {
	def main(args: Array[String]): Unit = {
		val arr = Array(1, 2, 4, 4, 4, 7, 9)
		val target = 4
		var lo = 0
		var hi = arr.length - 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

val arr = Array(1, 2, 4, 4, 4, 7, 9) and val target = 4 are immutable Scala bindings; the Array[Int] is read with arr(mid).
var lo = 0, var hi = arr.length - 1, and var result = -1 hold the mutable search window and not-found sentinel.
The loop is iterative: while (lo <= hi) keeps searching until the window is empty.
val mid = lo + (hi - lo) / 2 uses integer division on Int values while avoiding the direct (lo + hi) / 2 form.
On arr(mid) == target, the code records result = mid, then moves hi = mid - 1 to keep looking for an earlier duplicate.
If arr(mid) < target, it moves lo = mid + 1; otherwise it moves hi = mid - 1.
The trace starts with lo = 0, hi = 6: mid = 3 matches and records 3, mid = 1 reads 2 and moves lo to 2, then mid = 2 records the first occurrence.
When lo > hi, println(result) prints the exact result 2.

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

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