First Bad Version

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.

 1 public class Solution extends VersionControl {
 2     public int firstBadVersion(int n) {
 3         
 4         int left = 1;
 5         int right = n;
 6         
 7         while(left < right){
 8             int middle = left + (right-left) / 2;
 9             if(isBadVersion(middle)){
10                 right = middle;
11             }
12             else{
13                 left = middle+1;
14             }
15         }
16         return left;
17     }
18 }

这个问题比较简单，使用传统的二分查找算法即可。但是在使用二分查找的时候很多人会遇到一个小问题，即：如何计算中间值不会导致overflow。

有两种方法计算中间值：

middle = left + (right-left) / 2;

middle = (right + left) / 2;

这两种方法看似相同，但实际是有区别的。如果Middle是int类型，那么如果left和right数据很大时就可能导致（left + right）溢出，从而得不到正确结果。但是第一种方法不会导致溢出，推荐使用这种方法。

如果坚持使用第二种方法，middle的类型可以选择更长的数据类型。如果left和right是int，那么Middle可以使用long。