Open Shawngbk opened 7 years ago
middle = (low + (high - low)/2);与middle = (low + high)/2考虑溢出问题 nt型数据，java里除号是下取整的，二分法，你mid有不断增加的可能，加法就容易溢出，超过int型数据的表达范围，比如计算2个32位的数字，加法结果为64位，但是制定了数据类型为32位，结果就只能读这个64位数的低32位，这就是溢出。
有可能二分查找到数组的最后两个，如果数组的长度非常大，就有可能溢出
/* The isBadVersion API is defined in the parent class VersionControl. boolean isBadVersion(int version); */
public class Solution extends VersionControl { public int firstBadVersion(int n) { int low = 1; int high = n; int middle = 1; while(low <= high) { if(low == high) return low; middle = (low + (high - low)/2); if(isBadVersion(middle)) { high = middle; } else { low = middle + 1; } } return middle; } }
FB
Shawngbk
commented
7 years ago Shawngbk
commented
7 years ago
middle = (low + (high - low)/2);与middle = (low + high)/2考虑溢出问题 nt型数据，java里除号是下取整的，二分法，你mid有不断增加的可能，加法就容易溢出，超过int型数据的表达范围，比如计算2个32位的数字，加法结果为64位，但是制定了数据类型为32位，结果就只能读这个64位数的低32位，这就是溢出。
有可能二分查找到数组的最后两个，如果数组的长度非常大，就有可能溢出
/* The isBadVersion API is defined in the parent class VersionControl. boolean isBadVersion(int version); */
public class Solution extends VersionControl { public int firstBadVersion(int n) { int low = 1; int high = n; int middle = 1; while(low <= high) { if(low == high) return low; middle = (low + (high - low)/2); if(isBadVersion(middle)) { high = middle; } else { low = middle + 1; } } return middle; } }