First Bad Version


Time Complexity : O(log N)
Space Complexity : O(1)

This video explains a very important searching algorithm problem which is to find the first bad version in an array. We are not actually given the array but we can make API calls to find a particular array element is good or bad. Our goal is to minimize the API calls and find out the first bad version from left. I have shown the solving idea, intuition and similar problem which will help this solve this problem. I have shown proper example and solved it using binary search. The end of the video contains CODE explanation for the algorithm and CODE LINK is given below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful…CYA 🙂

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        long int low = 1;
        long int high = n;
        long int mid;
        long int result = n;
        
        while(low<=high)
        {
            mid = (low+high)/2;
            if(isBadVersion(mid))
            {
                result = mid;
                high = mid-1;
            }
            else
                low = mid+1;
        }
        return result;
    }
};

Write a comment