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 Scala DSA version keeps the same data and final output as every other DSA book in this wave.

Basic Implementation

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

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

    1object Main {2	def main(args: Array[String]): Unit = {
    values this step[1, 2, 4, 4, 4, 7, 9]arr4target-1result

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

    8while (lo <= hi) {9	val mid = lo + (hi - lo) / 210	if (arr(mid) == target) {
    values this step6 → 2hi3mid3result0lo

  3. lo ← 2, mid ← 1

    8while (lo <= hi) {9	val mid = lo + (hi - lo) / 210	if (arr(mid) == target) {
    values this step0 → 2lo1mid2hi3result

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

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

  5. stdout ← 2

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

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.