First Bad Version

L5 Medium Binary Search

Concept

When an array is monotonic (false...false, true...true), binary search can find the boundary efficiently instead of scanning linearly.

You have n versions numbered 1 through n. A helper isBad(version) returns true once a version is broken, and stays broken for every later version. Return the smallest version that is broken.

Examples

▸ n = 5, bad = 4

→ 4

▸ n = 1, bad = 1

→ 1

▸ n = 3, bad = 1

→ 1

Progressive Hints

Hint 1 · Nudge

Once it turns bad it stays bad, so the answer is the first 'yes' in a row of no's.

Hint 2 · Plan

Binary search between 1 and n. If the middle version is bad, the first bad one is at or before it, so tighten the upper bound. Otherwise it lies strictly after, so tighten the lower bound.

Hint 3 · Approach

lo = 1, hi = n. While lo < hi: mid = the middle; if isBad(mid) then hi = mid else lo = mid + 1. Return lo.

Output

// Run your code to see the output here.