In this article, we are going to see how to solve the following searching problem in minimum time complexity? This problem can be featured in any interviews. Submitted by Radib Kar, on January 18, 2019

## Problem statement

Suppose that IncludeHelp turns to be 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. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose we have n versions [1, 2, ..., n] and we want to find out the first bad one, which causes all the following ones to be bad.

Our product manager is given an API bool isBadVersion(version) which will return whether version is bad or not. He now wants to hire a programmer to implement a function to find the first bad version. There should be minimum number of calls to the API. Can you help him out?

## Solution Approach

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

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;
//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
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};

return A[version];
}

while(low<=high){
//narrow down factor
int mid=low+(high-low)/2;
return mid+1;
else
high=mid-1;
}
else
low=mid+1;
}
return -1;
}

if(i==1){
return i+1;
else
return -1;
}
}

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};
cout<<"product versions are:\n";
for(int i=0;i<n;i++){
cout<<i+1<<"\t";
if(A[i])
else
cout<<"good"<<endl;
}

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