※ 引述《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 来介接. 这份程式码存
在其他如有号/无号数的转型问题就不多做说明了.