Suppose that we have a product company & we have a product manager leading a team to develop a new product. Unfortunately, the latest version of our product fails the quality check

Of course this is a searching problem & for optimization we can do a binary search here. But now the question is, is there any other optimum searching method for search problem? The answer is yes.

It is binary search but the narrow down constant, K is not typically (low + high)/2 as in case of general binary search.

In this case the narrow down constant, K= low+(high-low)/2 resulting in much more optimized result.

Algorithm:

We have already the API function bool isBadVersion(version)

Now to find the first bad version we generate another function:

low=lower bound variable
high=upper bound variable

FUNCTION findFirstBad( int low, int high)
    While(low<=high){
        1.  Set mid to the narrow down constant K, low+(high-low)/2;
        2.  IF (isBadVersion(mid))  //if it is bad
            //there can be two case
            //1.    This is no 1, so thdere is no other version previously 
            //      thus these must be the first one
            //2.    The immediate previous one is not bad, thus this is 
            //      the first bad one
            IF (mid==1 || !isBadVersion(mid-1))
                Return mid;
            ELSE
                //narrow down high as first bad one must be before this one
                high=mid-1;
            End IF-ELSE
        ELSE
            //since this is not bad, the lower bound must be > this version
            low=mid+1;
        END IF-ELSE
        3.  If not returned from while loop, no bad version exists at all
        Return -1;
    END WHILE
END FUNCTION

C++ implementation

#include <bits/stdc++.h>
using namespace std;

#define n 10

int A[n]= { 0, 0, 0, 0, 0, 0, 1, 1, 1, 1};

// declaration of isBadVersion API.
bool isBadVersion(int version){
	return A[version];
}

int findFirstBad(int low,int high){
	while(low<=high){
		//narrow down factor
		int mid=low+(high-low)/2;
		if(isBadVersion(mid)) {
			if(mid==0 || !isBadVersion(mid-1))
				return mid+1;
			else
				high=mid-1;
		}
		else
			low=mid+1;
	}
	return -1;	
}

int firstBadVersion(int i) {
	if(i==1){
		if(isBadVersion(i))
			return i+1;
		else
			return -1;
	}
	return findFirstBad(0,i);
}

int main(){
	cout<<"this is a functional problem,so main functiom hardcoded\n";
	//product versions
	//A[n]= { 0, 0, 0, 0, 0, 0, 1, 1, 1, 1};
	//0=good product, 1=bad product
	cout<<"product versions are:\n";
	for(int i=0;i<n;i++){
		cout<<i+1<<"\t";
		if(A[i])
			cout<<"bad"<<endl;
		else
			cout<<"good"<<endl;
	}
	
	cout<<"First Bad version is:\n";
	cout<<firstBadVersion(n-1);
	
	return 0;
}

Output

this is a functional problem,so main functiom hardcoded
product versions are:
1       good
2       good
3       good
4       good
5       good
6       good
7       bad
8       bad
9       bad
10      bad
First Bad version is:
7