Searching

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.ts 
const arr: number[] = [1, 2, 4, 4, 4, 7, 9];
const target: number = 4;
let lo: number = 0;
let hi: number = arr.length - 1;
let result: number = -1;
while (lo <= hi) {
  const mid = lo + Math.floor((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.log(result);

Complexity

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

Implementation notes

  • TypeScript declares arr: number[], target: number, and local index state lo, hi, and result as number values.
  • result starts at -1 as the miss sentinel. Each loop computes const mid = lo + Math.floor((hi - lo) / 2) and reads arr[mid].
  • The hit check uses strict equality, arr[mid] === target. On a match the code records result = mid and moves hi = mid - 1, so duplicate matches keep searching left for the first index.
  • Numeric comparison arr[mid] < target moves lo = mid + 1; the remaining branch moves hi = mid - 1.
  • The replay records lo=0, hi=6, mid=3, result=3, then lo=0, hi=2, mid=1 moving right, then lo=2, hi=2, mid=2, result=2, and exits when lo > hi.
  • console.log(result) prints 2. The array is never mutated; visible allocation is the input number[], while the search updates scalar bindings only.
execution replay The checked-in replay follows the language-neutral state table for `search-binary-first`.
cross-language comparison This TypeScript DSA version keeps the same data and final output as every other DSA book in this wave.