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. 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?

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,Kis 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

C++ implementationOutput