278. First Bad Version

Time: O(log n)

Space: O(1)

Intuition

Classic binary search for the leftmost true condition. If isBadVersion(mid) is true, the first bad version is at mid or earlier (hi = mid). If false, it's after mid (lo = mid+1).

Algorithm

1lo = 1, hi = n.
2While lo < hi: mid = lo + (hi-lo)/2.
3If isBadVersion(mid): hi = mid. Else: lo = mid+1.
4Return lo.

Example Walkthrough

Input: n = 5, bad = 4

1.lo=1,hi=5. mid=3: not bad -> lo=4.
2.lo=4,hi=5. mid=4: bad -> hi=4.
3.lo=hi=4. Return 4.

Output: 4

Common Pitfalls

•Use hi=mid (not mid-1) to not skip the first bad version itself.

278.cs

/* The isBadVersion API is defined in the parent class VersionControl.
      bool IsBadVersion(int version); */

// Approach: Binary search for the leftmost position where IsBadVersion returns true.
// Maintain lo = 1 and hi = n; at each step compute mid = lo + (hi - lo) / 2 (avoids overflow).
// If IsBadVersion(mid) is true, the first bad version is at mid or earlier: set hi = mid.
// If false, the first bad version is strictly after mid: set lo = mid + 1.
// When lo == hi, we have found the first bad version.
// Using hi = mid (not mid - 1) ensures we never skip the answer.
// Time: O(log n) Space: O(1)

public class Solution : VersionControl
{
    public int FirstBadVersion(int n)
    {
        int l = 1;
        int r = n;

        while (l < r)
        {
            int m = l + (r - l) / 2;
            if (IsBadVersion(m))
                r = m;
            else
                l = m + 1;
        }

        return l;
    }
}

Was this solution helpful?