278. First Bad Version

二刷 06/2022

Time O(logN)

Space O(1)

Runtime: 14 ms, faster than 97.88% of Java online submissions for First Bad Version.

Memory Usage: 40.3 MB, less than 77.89% of Java online submissions for First Bad Version.

/* 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 (super.isBadVersion(mid)) {

                end = mid;

            } else {

                start = mid + 1;

            }

        }

        return start;

    }

}

一刷
Binary Search
O(logn)
99.77 %
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        // f  f  t  t  t
        int start = 1;
        int end = n;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (isBadVersion(mid)) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }
}