278. First Bad Version

#binary-search

Problem

First Bad Version - LeetCodeLeetCode

Intuition

Time Complexity

Space Complexity

Solution

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

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        // Time Complexity: O(log n);
        // Space Complexity: O(1), auxillary space, no extra space is used
        
        // Initialise low as low - 1 compared to starting value
        // high as "n"
        int low = 0, high = n;

        // Search space is monotonically increasing
        // If a version fails, then all versions after it also fail.
        
        // We need to find the first bad version, i.e. minimize the bad versions
        // such that we need to find the first one. So in case of minimization,
        // the high will be moving towards leff, minimizing the search space.

        // Low contains invalid values
        // High contains all possible valid values [1...n]

        while(low + 1 < high) {
            int mid = low + (high-low)/2; // Find the mid
            if(isBadVersion(mid)) { 
                high = mid;
            } else {
                low = mid;
            }
        }

        // When the condition (low + 1 < high) is broken, the high will be at first bad version
        // as we are trying to find the minimum  bad version
        return high;
    }
}