First Bad Version Problem


Description

LeetCode Problem 278.

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 returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example 1:

1
2
3
4
5
6
7
Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5)-> true
call isBadVersion(4)-> true
Then 4 is the first bad version.

Example 2:

1
2
Input: n = 1, bad = 1
Output: 1

Constraints:

  • 1 <= bad <= n <= 2^31 - 1


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {
public:
    int firstBadVersion(int n) {
        long long l, m, r, pos;
        l = 1, r = n; 
        while (l <= r) {
            m = (l + r) / 2;
            if (isBadVersion(m)) {
                pos = m;
                r = m - 1;
            }
            else 
                l = m + 1;
        }
        return pos;
    }
};




Related Posts

Find K-Th Smallest Pair Distance Problem

LeetCode 719. The distance of a pair of integers a...

Binary Search Problem

LeetCode 704. Given an array of integers nums which is...

Random Point In Non-Overlapping Rectangles Problem

LeetCode 497. You are given an array of non-overlapping axis-aligned...

Split Array Largest Sum Problem

LeetCode 410. Given an array nums which consists of non-negative...

Smallest Good Base Problem

LeetCode 483. Given an integer n represented as a string,...

Single Element In A Sorted Array Problem

LeetCode 540. You are given a sorted array consisting of...