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

const arr = [1, 2, 4, 4, 4, 7, 9];
const target = 4;
let lo = 0;
let hi = arr.length - 1;
let result = -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

JavaScript stores arr as a const Array of Number values and searches it without mutating the array or calling a library helper.
The iterative loop keeps let lo, let hi, and let result = -1 as local numeric bindings. result is the miss sentinel until a matching index is recorded.
Each probe computes const mid = lo + Math.floor((hi - lo) / 2), then reads arr[mid]. Strict equality, arr[mid] === target, records a match and moves hi = mid - 1 so duplicates are searched to the left; arr[mid] < target moves lo = mid + 1.
The replay shows lo=0, hi=6, mid=3 matching 4 and recording result=3, then lo=0, hi=2, mid=1 moving right because 2 < 4, then lo=2, hi=2, mid=2 recording the first occurrence result=2.
console.log(result) prints 2. Runtime allocation is limited to the input array and the output formatting; the search itself only updates scalar bindings, so it adds no ongoing GC pressure.

execution replay The checked-in replay follows the language-neutral state table for `search-binary-first`.

cross-language comparison This JavaScript DSA version keeps the same data and final output as every other DSA book in this wave.