278. First Bad Version

Source link: https://leetcode.com/problems/first-bad-version/

Design

The problem could be simply solved by the binary search approach. The process is shown below:

Assume g is the good version, and b is a bad version

First bad version

Implementation

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
  public int firstBadVersion(int n) {
    int start = 1, end = n;
    while (start < end) {
      int mid = start + (end - start) / 2;
      if (isBadVersion(mid)) {
        end = mid;
      } else {
        start = mid + 1;
      }
    }
    return start;
  }
}

Complexity Analysis

Time: $O(logn)$

Space: $O(1)$