This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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.

**Credits:**

Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

b'

\n## Summary

\n## Solution

\n

\n#### Approach #1 (Linear Scan) [Time Limit Exceeded]

\n

\n#### Approach #2 (Binary Search) [Accepted]

\n\n\n

'
\n\n

\nThis is a very simple problem. There is a subtle trap that you may fall into if you are not careful. Other than that, it is a direct application of a very famous algorithm.

\n\n

The straight forward way is to brute force it by doing a linear scan.

\n\n**Complexity analysis**

- \n
- \n
Time complexity : .\nAssume that takes constant time to check if a

\n*version*is bad. It takes at most checks, therefore the overall time complexity is . \n - \n
Space complexity : .

\n \n

\n

It is not difficult to see that this could be solved using a classic algorithm - Binary search. Let us see how the search space could be halved each time below.

\nScenario #1: isBadVersion(mid) => false\n\n 1 2 3 4 5 6 7 8 9\n G G G G G G B B B G = Good, B = Bad\n | | |\nleft mid right\n

Let us look at the first scenario above where . We know that all versions preceding and including are all good. So we set to indicate that the new search space is the interval (inclusive).

\nScenario #2: isBadVersion(mid) => true\n\n 1 2 3 4 5 6 7 8 9\n G G G B B B B B B G = Good, B = Bad\n | | |\nleft mid right\n

The only scenario left is where . This tells us that may or may not be the first bad version, but we can tell for sure that all versions after can be discarded. Therefore we set as the new search space of interval (inclusive).

\nIn our case, we indicate and as the boundary of our search space (both inclusive). This is why we initialize and . How about the terminating condition? We could guess that and eventually both meet and it must be the first bad version, but how could you tell for sure?

\nThe formal way is to prove by induction, which you can read up yourself if you are interested. Here is a helpful tip to quickly prove the correctness of your binary search algorithm\nduring an interview. We just need to test an input of size 2. Check if it reduces the search space to a single element (which must be the answer) for both of the scenarios above. If not, your algorithm will never terminate.

\nIf you are setting , you have to be very careful. Unless you are using a language that does not overflow such as Python, could overflow. One way to fix this is to use instead.

\nIf you fall into this subtle overflow bug, you are not alone. Even Jon Bentley\'s own implementation of binary search had this overflow bug and remained undetected for over twenty years.

\n\n**Complexity analysis**

- \n
- \n
Time complexity : .\nThe search space is halved each time, so the time complexity is .

\n \n - \n
Space complexity : .

\n \n