278. First Bad Version

EasyView on LeetCode

Array Binary Search

Time: O(log n)

Space: O(1)

Problem Overview

Classic binary search for the leftmost true condition.

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?