C++: First Bad Version

Thought Process

Binary Search is the optimal approach for this problem. By dividing the search space in half at each step, we can efficiently find the first bad version. The key is to adjust the search range based on whether the current midpoint is a bad version or not. We continue this process until we've narrowed down to the exact version where the transition from good to bad occurs. 

class Solution {
public:
    int firstBadVersion(int n) {

        int start = 1;
        int end = n;

        while(start<=end){

            int mid = end - (end-start)/2; 

            if(isBadVersion(mid))
                end = mid-1;
            else
                start = mid+1;
        }
        return start;
    }
};

Code Complexity

Time Complexity: O(log n)

The algorithm uses binary search, which halves the search space at each step, resulting in a logarithmic time complexity.

Space Complexity: O(1)

The algorithm uses a constant amount of extra space, regardless of the input size.

Code copied!