# 278. First Bad Version

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Mfr_Fo3vqpFd-MRBiOY%2F-Mfr_aVJbB0jHw2mNCLO%2Fimage.png?alt=media\&token=2857ac64-c4ba-4160-90d3-4fa7b92a838a)

time: O(logn)

space: O(1)

```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) {
        // 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
```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

```java
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;
    }
}
```
