278. First Bad Version

Versions 1..n are released in order and every version after a bad one is also bad. Using isBadVersion(v), find the first bad version with as few calls as possible. Here `bad` is the hidden first bad version.

Versions go good, good, …, bad, bad. Binary search for the first bad one: if mid is bad the answer is at or left of mid, otherwise it is right of mid.

1function solution(isBadVersion: (v: number) => boolean) {
2  return (n: number): number => {
3    let lo = 1, hi = n;
4    while (lo < hi) {
5      const mid = lo + ((hi - lo) >> 1);
6      if (isBadVersion(mid)) hi = mid;
7      else lo = mid + 1;
8    }
9    return lo;
10  };
11}