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

Basic Implementation

basic.cs
Replay: real traced execution (multi-file project)
using System;

class Program {
	static void Main() {
		int[] arr = new int[] { 1, 2, 4, 4, 4, 7, 9 };
		int target = 4;
		int lo = 0;
		int hi = arr.Length - 1;
		int result = -1;
		while (lo <= hi) {
			int 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;
			}
		}
		Console.WriteLine(result);
	}
}

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

    1using System;
    values this step[1, 2, 4, 4, 4, 7, 9]arr4target-1result

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

    10while (lo <= hi) {11	int mid = lo + (hi - lo) / 2;12	if (arr[mid] == target) {
    values this step6 → 2hi3mid3result0lo

  3. lo ← 2, mid ← 1

    10while (lo <= hi) {11	int mid = lo + (hi - lo) / 2;12	if (arr[mid] == target) {
    values this step0 → 2lo1mid2hi3result

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

    10while (lo <= hi) {11	int mid = lo + (hi - lo) / 2;12	if (arr[mid] == target) {
    values this step2 → 1hi3 → 2result2mid2lo

  5. stdout ← 2

    1using System;
    values this step2stdout2result

Complexity

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

Implementation notes

  • Keep the explicit loop instead of calling BCL search helpers so the replay can show lo, hi, mid, and the saved result after each comparison.
  • int mid = lo + (hi - lo) / 2 avoids overflowing the midpoint addition, and each arr[mid] read from the managed reference int[] is bounds-checked by the CLR.
  • On equality, C# records result = mid and moves hi = mid - 1, preserving the duplicate-left search rather than stopping at any matching index.