Bridge · From syntax to engineering · 25 MIN

Find the first matching value with binary search

Maintain a search interval whose boundaries have precise meanings.

Use a half-open interval [low, high): low is included and high is excluded. Every value before low is smaller than the target; every value at or after high is at least the target. Each comparison removes half the remaining interval. Moving high to mid, instead of returning on equality, keeps searching for the first duplicate. Once the interval is empty, check whether the target actually exists. Binary search needs ordered input; sorting inside every lookup changes both the complexity and the meaning of returned indexes.

Write a small contract first, then test how the implementation behaves at its boundaries.

Read the example

const values = [2, 4, 4, 8];
console.log(values[1] === 4);

true

Your challenge

Input {values:sorted ascending integers, target:integer}. Return the first index of target or -1 if absent. Leave values unchanged and use O(log n) comparisons.

Solution cost: O(log n). time · O(1), excluding input. space

Common trap

Returning immediately on equality may return any duplicate instead of the first.

Further reading: MDN while