我有一個任務要編寫一個二進制搜索，它返回我們正在尋找的值的第一次迭代。我一直在網上做一些研究，我的搜索看起來很像我正在尋找的東西，但我遇到了問題。如果我將此代碼傳遞給一個看起來像 {10,5,5,3,2} 的數組，它會在中間找到 5（它檢查的第一件事），然后返回它。但這不是 5 的第一次迭代，而是第二次迭代。我究竟做錯了什么？這甚至可能嗎？提前致謝！代碼（我正在使用Java）：public static int binarySearch(int[] arr, int v){ int lo = 0; int hi = arr.length-1; while(lo <= hi){ int middle = (lo+hi)/2; if(v == arr[middle]){ return middle; } else { if(v < arr[middle]){ lo = middle+1; } else { hi = middle-1; } } } return -1;}
1 回答
千巷貓影
TA貢獻1829條經驗 獲得超7個贊
這是一個有效的修改算法。
public static int binarySearch(int[] arr, int v) {
int lo = -1;
int hi = arr.length - 1;
while (hi - lo > 1 ) {
int middle = (lo + hi) / 2;
if (arr[middle] > v) {
lo = middle;
} else {
hi = middle;
}
}
if (v == arr[hi]) {
return hi;
} else {
return -1;
}
}
關鍵點是：
區間 (lo, hi] 不包括左側，包括右側。
在每一步，我們都會丟棄一半的間隔。當我們下降到一個元素時，我們就會停下來。提前終止的嘗試只能提供最小的性能提升，而它們通常會影響代碼的易讀性和/或引入錯誤。
當
arr[middle] = v我們分配hi = middle時，因此丟棄了右半部分。這是安全的，因為我們不關心v過去的任何事件middle。我們確實關心arr[middle]，它可能是第一次出現也可能不是第一次出現，正是出于這個原因，我們將 (lo, hi] 包含在右邊。如果出現vbeforemiddle，我們將在后續迭代中找到它們。作為旁注，更自然的定義
[0, n)包含在左側，排除在右側，可用于查找v.
以我的經驗，這種包容-排斥的區間定義產生了最短、最清晰和最通用的代碼。人們一直在努力改進它，但他們經常陷入困境。
添加回答
舉報
0/150
提交
取消