# First Bad Version  Difficulty Level Easy
Binary Search

We all have heard the saying “Bad Apple Ruins The Bunch”.First Bad Version is a problem that beautifully illustrates the same. Today we have a problem which is First Bad Version. One of the interns has made an nth bad commit due to which commits from n+1 have all been facing merge conflicts. The task in hand is pretty simple. All we have to do is “search” for the first bad commit that leads to the downfall of our software. However, we can only check if ith commits isBadVersion() and we have very limited calls.

Taking it from the top. Let us look at a test case

Input

n=6 and version=3 is the faulty commit

Helping us detect the first bad version

Output

3

## Approach-1  ### Linear Search

The first and easy approach that might come to our mind would be using a linear search.

We look through each of the elements starting from 0 one by one

Let us look at that by the code.

## Implementation  ### Java Code For First Bad Version

```public class Solution extends VersionControl
{
{
int ans=0;
for(int i=0;i<n;i++)
{
{ans=i;break;}
}
return ans;
}
}```

### C++ Code For First Bad Version

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

class Solution
{
public:
{
int ans=0;
for(int i=0;i<n;i++)
{
{ans=i;break;}
}
return ans;
}
};```

## Complexity Analysis  The time complexity of the above approach=O(n)

Why?

• We go through each and every version until we encounter the third version and term it as bad
• In the worst case, we end up going to the last element in the search of the bad one
• Thus, leading the time complexity to O(n) i.e linear
Find the minimum distance between two numbers

This, however, leads to a timeout.

## Approach-2  ### Binary Search

The linear search may give off a timeout for a few of the test cases which can efficiently be countered with the help of a binary search.

We look out for the mid element each time cutting the time involved considerably. Assuming we have 256 versions and 255th is the bad one.

The first mid=(0+256)/2=128. We check the 128th version.

• If it is bad then we go and check the previous half.
• We calculate 0+(128-0)/2=64 and repeat the process
• The version if is good we check the later half.
• We calculate 128+(256-128)/2=192 and repeat the process

We calculate the mid and check if the version is good or bad.

Let us look into the code.

## Implementation  ### Java Code

```/* The isBadVersion API is defined in the parent class VersionControl.

public class Solution extends VersionControl
{
{
int st=1;
int en=n;
int ans=n;
while(st<=en)
{
int mid=st+(en-st)/2;
{ans=mid;en=mid-1;}
else
st=mid+1;
}
return ans;
}
}```

### C++ Code

```class Solution
{
public:
{
int st=1;
int en=n;
int ans=n;
while(st<=en)
{
int mid=st+(en-st)/2;
{ans=mid;en=mid-1;}
else
st=mid+1;
}
return ans;
}
};```
```n=5

`3`

## Complexity Analysis  Time complexity=O(log n)

• In each search depending on the search, we search in the respective half
• We are halving our search space each and every time we proceed on to the next search
• Let us assume we make k calls
• Till when do we make these calls?
• Till we have only one search element we are looking at
• Thus, 2^k=n
• Taking log both sides k=log(n)
• Thus, making the time complexity log(n)
Two Sum Leetcode Solution

We might consider a ternary search as well.

But in many cases, it has been proven that binary search works better than the ternary search. Thus, we should consider the above-suggested search mechanism.

References

Now that we have gone through the problem. Wanna check it out for more complex data structures? 