So as a binary search, if you are aware of taking notes on the last_valid index or value, this pattern could solve a lot searching questions. As long as you nail down what is the last valid states you are looking for.

```
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
class Solution {
public:
// find the last good version 看我出神入化的二分查找
int search(int left, int right) {
// assume the last good is version 0, so if the actually bad starts from version 1 （the beginning）
// then the 0 will be the last good version number.
int last_good = 0;
while (left <= right) {
int mid = left + (right - left) /2 ;
if (isBadVersion(mid)) {
right = mid - 1;
} else {
last_good = mid;
left = mid + 1;
}
}
return last_good+1; // hah, +1 to become the first bad version.
}
int firstBadVersion(int n) {
return search(1, n);
}
};
```