leetcode day 16: lowest bad version

Given a function isBadVersion and a range of versions from 1 to N, find the lowest-numbered version that is “bad” as efficiently as possible.

This is another binary search, and I had a little less trouble with it. A few more and I’ll be able to knock one out right the first time. Since there weren’t any pointers or indexes or arrays to manage, this was easier. Still got tripped up on the order of testing, but when I sat down and delineated the terminal cases by hand I was able to easily code it.

Performance was excellent: 100% on CPU time, 95% on memory. Would be a win in an interview.

/** 
 * Forward declaration of isBadVersion API.
 * @param   version   your guess about first bad version
 * @return true if current version is bad 
 *	   false if current version is good
 * func isBadVersion(version int) bool;
 */

func firstBadVersion(n int) int {
    // Binary search it.
    // n is candidate.
    lowBound := 1
    highBound := n

    if isBadVersion(lowBound) {
        // short-circuit: if lowest possible version is bad,
        // no search is needed.
        return lowBound
    }

    // Now search between the bounds for the switchover point. Low is good,
    // high is bad.
    for {
        fmt.Println("Bad version between", lowBound, highBound)
        midpoint := (highBound+lowBound) / 2
        isBad := isBadVersion(midpoint)
        if isBad {
            highBound = midpoint
            if midpoint == lowBound+1 {
                 // midpoint is 1st bad above lowbound (known good)
                return midpoint
            }
        } else {
            lowBound = midpoint
            if highBound == midpoint+1 {
                // midpoint is good, 1 above is bad, so that's it
                return highBound
            }
        }
    }
}

Weirdly, removing the debug made it slower. 81st percentile CPU.

Which pretty much goes to show that trying to rate efficiency of code via leetcode is probably a bad idea.