如果陣列中不存在元素，如何使用二進制搜索找到元素的下限
輸入：陣列大小，元素
5 4
陣列元素：
1 2 3 7 8
輸出：2 [這是下界的索引]
while(low <= high){
int mid = (high low)/2;
if(a[mid] < s){
low = mid 1;
}
else if(a[mid] >= s){
high = mid - 1;
}
}
測驗用例 1 測驗用例 2
uj5u.com熱心網友回復：
我不會提供我認為是家庭作業的代碼。但我會提供建議，因為您必須小心才能正確獲取二進制搜索的邊緣情況。任何人都花了很多年才產生一個正確的實作，大多數教科書的解決方案在很長一段時間內都是錯誤的，大多數專業程式員都在為這個問題苦苦掙扎。
我發現區分二進制搜索的三種變體非常有幫助。它們可以這樣編碼：
-- Version 1.
while (low < high) {
int mid = (low high) / 2;
if (some condition on mid) {
low = mid;
} else {
high = mid-1;
}
}
-- Version 2.
while (low < high) {
int mid = (low high) / 2;
if (some condition on mid) {
low = mid 1;
} else {
high = mid;
}
}
-- Version 3.
while (low <= high) {
int mid = (low high) / 2;
if (lower bound condition on mid) {
low = mid 1;
} else if (upper bound condition on mid) {
high = mid-1;
}
else {
break, return, or otherwise indicate we have an answer
}
}
前兩個版本以low == high == the only possible answer. 使用哪一個需要仔細考慮condition告訴您的內容mid。
第三個版本用于在陣列中搜索特定值。這是一個具體但重要的案例，但是我的大多數二進制搜索看起來都不是這樣。
現在，在您的情況下，您需要 2 次搜索。首先是找到值為下限的 LAST 索引。第二個是找到該值第一次出現的索引。我不認為我放棄太多，說我不會以同樣的方式寫那些。
祝你好運，希望這個問題能讓你在完成后更好地理解二分搜索！
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/489538.html