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

Basic Implementation

basic.swift
Replay: real traced execution (multi-file project)
let arr = [1, 2, 4, 4, 4, 7, 9]
let target = 4
var lo = 0
var hi = arr.count - 1
var result = -1
while lo <= hi {
	let 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
	}
}
print(result)

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

    1let arr = [1, 2, 4, 4, 4, 7, 9]2let target = 4
    values this step[1, 2, 4, 4, 4, 7, 9]arr4target-1result

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

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

  3. lo ← 2, mid ← 1

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

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

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

  5. stdout ← 2

    16}17print(result)
    values this step2stdout2result

Complexity

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

Implementation notes

  • This checked source uses top-level Swift statements, not a helper function: let arr = [1, 2, 4, 4, 4, 7, 9] and let target = 4 are immutable [Int]/Int bindings.
  • var lo, var hi, and var result are the mutable search state; result starts at -1 as the not-found sentinel.
  • The loop guard is while lo <= hi, and let mid = lo + (hi - lo) / 2 uses integer division on Int values to choose the current index.
  • On arr[mid] == target, the code records result = mid and moves hi = mid - 1 so duplicates to the left stay visible; smaller values move lo = mid + 1.
  • The trace records mid = 3 setting result to 3 and hi to 2, then mid = 1 moving lo to 2, then mid = 2 updating the first occurrence to result = 2.
  • When lo > hi, print(result) writes the Swift integer output 2.