二分查找数据溢出问题

Posted on In Views:

278. 第一个错误的版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int firstBadVersion(int n) {
        if(n==1 || isBadVersion(1)){
            return 1;
        }
        int left=1,right=n;
        int mid;
        // mid = left + (right - left) / 2;
        mid=(left+right)/2;
        while (left<right){
            if(isBadVersion(mid)==false ){
                left=mid;
            }else{
                right=mid;
            }
            if(left+1==right){
                return right;
            }
            // mid = left + (right - left) / 2;
            mid=(left+right)/2;
        }
        return right;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int firstBadVersion(int n) {
        if(n==1 || isBadVersion(1)){
            return 1;
        }
        int left=1,right=n;
        int mid;
        mid = left + (right - left) / 2;
        // mid=(left+right)/2;
        while (left<right){
            if(isBadVersion(mid)==false ){
                left=mid;
            }else{
                right=mid;
            }
            if(left+1==right){
                return right;
            }
            mid = left + (right - left) / 2;
            // mid=(left+right)/2;
        }
        return right;
}

left和right相加可能会超出int类型的范围