我正在解決 LeetCode 上的這個問題278 First Bad Version。我已經使用二進制搜索來獲取元素。
在大陣列的情況下，我獲取陣列中間索引的方法m = (start end)/2會導致問題，更接近 int 的 MAX_LIMIT。首先，我想到了 int 范圍溢位問題，但我不確定，因為它可以正常作業，end = MAX_LIMIT有些start < MAX_LIMIT甚至超出了 int 范圍。
我想了解如何m = start (end - start)/2比m = (start end)/2
代碼 1 適用于輸入：
2147483647
98765432
但是代碼 1 輸入失敗：
2147483647
987654321
我認為溢位問題應該在兩種情況下都發生，或者都不發生。
1.m = (start end)/2適用于大型陣列但失敗的代碼
public int FirstBadVersion(int n) {
if(n == 1){
return 1;
}
int s = 1;
int e = n;
int x = 0;
while(s != e){
x = (s e)/2;
if(IsBadVersion(x)){
e = x;
}
else{
s = x 1;
}
}
return s;
}
2. 使用的代碼m = start (end - start)/2
public int FirstBadVersion(int n) {
if(n == 1){
return 1;
}
int s = 1;
int e = n;
int x= 0;
while(s != e){
// x = (s e)/2;
x = s (e-s)/2;
if(IsBadVersion(x)){
e = x;
}
else{
s = x 1;
}
}
return e;
}
uj5u.com熱心網友回復：
計算時有整數溢位
(a b) / 2
當(a b) > int.MaxValue總和(a b)不能表示為32 位整數（它需要33位），并且您有不正確（通常為負）的結果（當位33被忽略時），然后除以2.
我建議使用long以防止整數溢位：
public int FirstBadVersion(int n) {
// Special case: all versions starting from #1 failed
if (IsBadVersion(1))
return 1;
// let use long in order to avoid integer overflow
long correct = 1;
long failed = n;
// while we have unknown version between correct and failed
while (failed - correct > 1) {
int middle = (low high) / 2); // it safe now : adding two long values
if (IsBadVersion(middle))
failed = middle;
else
correct = middle;
}
return (int)failed;
}
如果使用long是作弊并且你想堅持int，你可以使用下面的公式，因為int a, b我們可以把（注意我們不添加大值a，b而是它們的一半）
(a b) / 2 == a / 2 b / 2 (a % 2 b % 2) / 2
請注意，您的公式不是通用的
(a b) = a (b - a) / 2;
它將在問題＃278 的特定情況下作業，其中a和b是積極的，但在一般情況下會失敗，比如何時a = 1_000_000_000, b = -2_000_000_000。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/517616.html
標籤：C＃数组二分搜索