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

Basic Implementation

basic.rs
Replay: real traced execution (multi-file project)
fn main() {
	let arr = [1, 2, 4, 4, 4, 7, 9];
	let target = 4;
	let mut lo: i32 = 0;
	let mut hi: i32 = (arr.len() as i32) - 1;
	let mut result: i32 = -1;
	while lo <= hi {
		let mid = lo + (hi - lo) / 2;
		if arr[mid as usize] == target {
			result = mid;
			hi = mid - 1;
		} else if arr[mid as usize] < target {
			lo = mid + 1;
		} else {
			hi = mid - 1;
		}
	}
	println!("{}", result);
}

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

    1fn main() {2	let arr = [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	let mid = lo + (hi - lo) / 2;9	if arr[mid as usize] == target {
    values this step6 → 2hi3mid3result0lo

  3. lo ← 2, mid ← 1

    7while lo <= hi {8	let mid = lo + (hi - lo) / 2;9	if arr[mid as usize] == target {
    values this step0 → 2lo1mid2hi3result

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

    7while lo <= hi {8	let mid = lo + (hi - lo) / 2;9	if arr[mid as usize] == 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

  • The checked source uses a fixed sorted array, let arr = [1, 2, 4, 4, 4, 7, 9], not a Vec or slice parameter.
  • This version does not return Option; it keeps let mut result: i32 = -1 as a not-found sentinel and prints that scalar at the end.
  • lo, hi, and mid are i32 values. hi starts as (arr.len() as i32) - 1, and array reads cast with arr[mid as usize].
  • The loop guard while lo <= hi keeps mid nonnegative for each read in this trace. Using signed bounds avoids usize underflow when hi = mid - 1.
  • The branch order checks equality first. On a match it records result = mid and narrows left with hi = mid - 1, so duplicates at indices 2, 3, and 4 return the first index.
  • The trace records mid=3 as a match (result=3, hi=2), mid=1 as value 2 (lo=2), then mid=2 as the leftmost match (result=2, hi=1).
  • println!("{}", result) uses display formatting and prints 2.