LeetCode May Challenge (19 Part Series)

### 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.
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
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.
// bool isBadVersion(int version);
class Solution {
private:
int binarySearch(int t)
{
int L = 1, U = t, result = -1;
while(L<=U)
{
int M = L + (U-L)/2;
bool badVersionResult = isBadVersion(M);
if(badVersionResult == true)
{
result = M;
U = M-1;
}
else {
L = M+1;
}
}
return result;
}
public:
int firstBadVersion(int n) {
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.

LeetCode May Challenge (19 Part Series)

## Discussion