Gamified challenge · Lower-bound binary search
Builds are numbered 1..n. Once a build is broken, every later build is broken too, and the newest build n is known to be broken. Each test of a build takes an hour, so you want to find the first broken build with as few tests as possible.
A real tester can't talk to your code, so its results come as data: isBad[i] is 1 if build i + 1 is broken, 0 if it works. Write firstBad(n, isBad) that returns the list of builds you test, in order. The checker replays them and requires that each test is a middle build of the builds still in doubt (either middle when their count is even), and that when you stop only one candidate for the first bad build is left. Never test a build whose result you already know.
Example: n = 10, first bad build 4. Builds 1..9 are in doubt. Test 5: broken, so the first bad build is in 1..5. Test 3 (a middle of the doubtful 1..4): it works, so the first bad build is in 4..5. Test 4: broken, so build 4 is pinned. Return [5, 3, 4]; [5, 2, 4, 3] (other middles) would also be accepted. With n = 1 nothing is in doubt, so return [].
This game is part of the paid plans. Sign in, then pick a plan to write your answer, watch it play out, and step through the algorithm with its guide.
Sign in with Google