DEV Community

Aroup Goldar Dhruba

Posted on • Updated on

Problem Statement

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your 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 you have `n` versions `[1, 2, ..., n]` and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API `bool isBadVersion(version)` which will return whether `version` is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example

``````Given n = 5, and version = 4 is the first bad version.

Then 4 is the first bad version.
``````

Solution thought process

If you have to find the first occurrence of an element in a sorted array of some kind, binary search should be the first thing we should be thinking of.

Let's think of the first scenario:

``````Scenario #1: isBadVersion(mid) => false

1 2 3 4 5 6 7 8 9
G G G G G G B B B       G = Good, B = Bad
|       |       |
left    mid    right
``````

If we can see that the isBadVersion is returning false for mid, we can adjust our `left` to be equal to `mid+1`, because we know that we don't have to consider previous [left, mid] region for the answer, as we can see it from the scenario #1.

``````Scenario #2: isBadVersion(mid) => true

1 2 3 4 5 6 7 8 9
G G G B B B B B B       G = Good, B = Bad
|       |       |
left    mid    right
``````

If we can see that isBadVersion is returning true for mid, we can adjust our right to be `mid-1` and our `result = mid` because we have to find the first occurrence of the bad product.

Solution

``````// The API isBadVersion is defined for you.

class Solution {
private:
int binarySearch(int t)
{
int L = 1, U = t, result = -1;
while(L<=U)
{
int M = L + (U-L)/2;
{
result = M;
U = M-1;
}
else {
L = M+1;
}
}
return result;
}
public:
return binarySearch(n);
}
};
``````

Complexity

Time complexity: O(logn), on every loop we are making the candidate space into half, giving it a logarithmic complexity.

Space Complexity: O(1), we are not assigning any additional array.

DEV Community

Timeless DEV post...

Git Concepts I Wish I Knew Years Ago

The most used technology by developers is not Javascript.

It's not Python or HTML.

It hardly even gets mentioned in interviews or listed as a pre-requisite for jobs.

I'm talking about Git and version control of course.