java方法:
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
//false是没出错,true是出错,强调一下,不然会陷入自闭状态,楼主第一次做的时候顶级自闭
//想半天想不通哪里出错,提交了n遍
//所以二分路线是这样的,false找右边,true就找左边
int l = 1 , h = n;
while(l < h){
int mid = l + (h - l) / 2;
if(isBadVersion(mid)){
h = mid;
}else{
l = mid + 1;
}
}
return l;
}
}
C++方法:
循环判断有等号
,循环中都要偏移,retrun left还是right需要辨别
class Solution {
public:
int firstBadVersion(int n) {
int left = 1;
int right = n;
while (left <= right) {
int mid = (right-left)/2 + left;
// 只考虑一段,另一端不断缩进
/* 理解:
需要找到第一个bad的状态
若当前mid不是,则闭区间[left, mid]之间全不是
那第一个至少是mid+1的状态
其余什么都不用想
让另一边right = mid - 1即可(因为循环中是有=的)
*/
if (!isBadVersion(mid)) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
};