```
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
/* public int firstBadVersion(int n) {
if(!isBadVersion(n)) {
return n;
} else {
return firstBadVersion(n-1);
}
}*/
/* public int firstBadVersion(int n) {
while(isBadVersion(n)) {
n -= 1;
}
return n;
}*/
public int firstBadVersion(int n) {
if(isBadVersion(n) == true && isBadVersion(n-1) != true ){
return n;
}
else if(isBadVersion(n/2)) {
return search(1, n/2);
} else {
return search(n/2,n);
}
}
//checking in first half or second half
public int search(int first, int last) {
int mid =0;
while(first <= last) {
mid = (first+last) /2;
if(isBadVersion(mid)) {
if(!isBadVersion(mid -1)) {
return mid;
} else {
last = mid -1;
}
} else {
first = mid +1;
}
}
return first;
}
}
```