※ 引述《Kuba4ma ()》之銘言：
這裡的問題在於寫碼方式和語言習慣相左, 導致無法描述空區間,
以及避免儲存重複的資訊.
C/C++ 是用半開區間來描述資料範圍, 因此存取 letters 的合法索
引落在 [0, 3) 內, 在這種設計下基於陣列的 divide-and-conquer
演算法就可以簡單將空區間 (物件不存在) 判斷作為迴圈終止條件:
size_t left = 0;
size_t right = letters.size();
// search in [left, right)
while (left < right) {
// divide [left, right) into 3 sub-intervals:
// 1. [left, m)
// 2. [m, m + 1) (only [m] itself)
// 3. [m + 1, right)
const size_t m = (left + (right - left) / 2);
assert(m < letters.size()); // m should be valid index
if (target < letters[m]) {
right = m; // search in [left, m)
// laters[m] <= target
} else {
left = m + 1; // search in [m + 1, right)
}
}
在迴圈結束後, left 的值只有兩種可能: 小於 3 或者等於 3. 只
要根據這兩種結果來印值, 不需要另外定義變數儲存相同資訊.
assert(left <= letters.size());
if (left == letters.size()) {
cout << letters[0] << endl;
} else {
cout << letters[left] << endl;
}
任何物件都被視為單個元素的陣列, 掌握這個概念就可以和所有的
標準函式庫函式, 尤其是 STL algorithms 來介接. 這份程式碼存
在其他如有號/無號數的轉型問題就不多做說明了.