278. First Bad Version

time: O(logn)

space: O(1)

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

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        // true true bad
        int start = 1;
        int end = n;
        
        while (start < end) {
            int mid = (start + end) >>> 1;
            boolean isBad = isBadVersion(mid);
            if (isBad) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }
}

latest version!

```java
/* 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 left = 1;
        int right = n;
        
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (isBadVersion(mid)) {
                if (!isBadVersion(mid-1)) {
                    return mid;
                }
                
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

/*
 all the versions after a bad version are also bad.
 
so when we find a bad version, we can check pre is good?
if it's good, means we find the first "bad version"! no need to think return left or right!
*/
```

or like this

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1;
        int right = n;

        while (left <= right) {
            int mid = left + (right - left)/2;
            if (isBadVersion(mid)) {
                if (mid - 1 >= 1 && isBadVersion(mid - 1)) {
                    right = mid - 1;
                } else {
                    return mid;
                }
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}