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

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)

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.

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.