# 278. First Bad Version (Easy)

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have `n` versions `[1, 2, ..., n]` and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API `bool isBadVersion(version)` which will return whether `version` is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example:

```Given n = 5, and version = 4 is the first bad version.

```call isBadVersion(3) -> false

Then 4 is the first bad version. ```
```

## Solutions

``````class Solution extends VersionControl {

if (n == 1 || isBadVersion(1)) {
return 1;
}

return 2;
}

return bisect(1, n);
}

public int bisect(long left, long right) {
// be careful of the overflow issue
int mid = (int) ((right + left) / 2);

// outlet of recursion
return mid;
}

// if version mid is contaminated the first bad version must be earlier but
// not equal to version mid. If the mid is the first bad, execution should never
// reach here and already exit from the above outlet
return bisect(left, mid - 1);
}

// if version mid is a fine version, search the consequent releases
return bisect(mid + 1, right);
}
}
``````
``````class Solution extends VersionControl {

return helper(1, n);
}

public int helper(long i, long j) {
// be careful of the overflow issue
int m = (int) ((j + i) / 2);

// actually, i > j will never happens since it already returned when i == j
if (i >= j) {
return (int) i;
}

// if version m is contaminate the first bad version must be earlier or equal to version m
return helper(i, m);
}

// if version m is a fine version, search the consequent releases
return helper(m + 1, j);
}
}
``````