278.First Bad Version

Posted on | In

Solution 1: accepted 18ms

Binary search.

Feel the differences and commonalities. The first solution is recommended, as it is a wild card solution. 

1
2
3
4
5
6
7
8
9
10
11
12
13
public int firstBadVersion(int n) {
    int lo = 1;
    int hi = n;
    while (lo + 1 < hi) {
        int mid = lo + (hi - lo) / 2;
        if (isBadVersion(mid)) {
            hi = mid;
        } else {
            lo = mid;
        }
    }
    return isBadVersion(lo)? lo : hi;
}
1
2
3
4
5
6
7
8
9
10
11
12
public int firstBadVersion(int n) {
    int lo = 1;
    int hi = n;
    while(lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (isBadVersion(mid))
            hi = mid;
        else 
            lo = mid + 1;
    }
    return lo; // hi is ok as well
}
1
2
3
4
5
6
7
8
9
10
11
12
public int firstBadVersion(int n) {
    int lo = 1;
    int hi = n;
    while(lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (isBadVersion(mid))
            hi = mid - 1;
        else 
            lo = mid + 1; 
    }
    return lo;  
}