# LeetCode 278. First Bad Version

## Description

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

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

## Explanation

Use binary search to find first bad version with O(logn) time complexity.

## Java Solution

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

public class Solution extends VersionControl {
int start = 1;
int end = n;

while (start + 1 < end) {
int mid = start + (end - start) / 2;
end = mid;
} else {
start = mid;
}
}

return start;
}
return end;
}
}``````

## Python Solution

``````# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool

class Solution:
"""
:type n: int
:rtype: int
"""
start = 1
end = n

while start + 1 < end:
mid = start + (end - start) // 2

end = mid
else:
start = mid

1. Iqbal Anwer says: