https://leetcode.com/problems/first-bad-version/description/
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.
time: log(n)
space: o(1)
1 public int firstBadVersion(int n) {
2 int left = 1, right = n;
3 while (left + 1 < right) {
4 int mid = left + (right - left) / 2;
5 if (isBadVersion(mid)) {
6 right = mid;
7 } else if (!isBadVersion(mid)) {
8 left = mid;
9 } else {
10 right = mid;
11 }
12 }
13 //post processing: same as first occurance
14 if (isBadVersion(left)) {
15 return left;
16 }
17 if (isBadVersion(right)) {
18 return right;
19 }
20 return -1;
21 }