2 minute read

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.

URL: https://leetcode.com/problems/first-bad-version/

The solution uses the binary search technique to find the target value. The target value is the lowest number that also returns true when the isBadVersion(number) method returns true. The naive approach would be to search linearly through the array to find the target value.

My solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        //calc mid point
        int p = 1, r = n;
        
        while (p <= r) {
            int q = p + (r-p)/2;
            if (isBadVersion(q) == true) {
                r = q - 1;
            }
            else {
                p = q + 1;
            }
        }
        return p;
    }
}

Explanation:
Line 7 initializes the lower bound, p, and the upper bound, r.

Line 9 is the main loop of the binary search algorithm. The loops condition is the traditional condition used for binary search.

Line 10 calculates the midpoint.

Line 11 is the first deviation from the traditional binary search algorithm. The if statement checks if the current value, q, is a bad version number. If true then search the left part of the array, [p,q-1] so that any smaller values that also are bad versions can be found. If false, then search the right part of the array, [q+1,r] so that a bad version number can be found.

Line 18 returns the minimum bad version of p. Before the loops terminates, p is equal to q. If isBadVersion(q) returns true, then p is the minimum bad version and r will be set to q - 1. If it returns false, then p is a good version number and p will be set q+1. In both cases, p will be the minimum bad version number.