使用二分查找算法寻找数组中大于目标值的最小字母

给定一个非递减排序的字符数组letters和一个字符target，返回数组中大于target的最小字符。注意字母具有循环特性，例如当target为'z'且letters为['a','b']时，答案为'a'。

示例 #

• 输入：letters = ["c","f","j"], target = "a"，输出："c"
• 输入：letters = ["c","f","j"], target = "c"，输出："f"
• 输入：letters = ["c","f","j"], target = "d"，输出："f"

约束条件 #

• 2 <= letters.length <= 10^4
• letters[i]为小写英文字母
• letters按非递减顺序排列
• letters至少包含两个不同字符
• target为小写英文字母

现有代码问题 #

你当前的代码在处理letters[mid] == target的情况时，错误地将res赋值为target，这不符合题目要求——我们需要找的是大于target的字符，等于的情况不能作为结果。比如测试用例["c","f","j"],"c"，代码最后返回了"c"，但正确结果应该是"f"。另外，代码也没有处理循环特性的场景：当所有字符都小于等于target时，应当返回数组的第一个元素。

修正后的代码 #

function nextGreatestAlphabet(letters, target) {
    let left = 0;
    let right = letters.length - 1;
    // 初始值设为数组第一个元素，处理循环场景
    let res = letters[0];
    while (left <= right) {
        let mid = Math.floor(left + (right - left) / 2);
        if (letters[mid] > target) {
            // 找到更大的字符，更新结果并向左搜索更小的候选
            res = letters[mid];
            right = mid - 1;
        } else {
            // 等于或小于target时，继续向右搜索更大的字符
            left = mid + 1;
        }
    }
    return res;
}

console.log(nextGreatestAlphabet(["c","f","j"],"c")); // 输出"f"
console.log(nextGreatestAlphabet(["a","b"],"z")); // 输出"a"

修正说明 #

1. 初始化结果值：将res初始化为letters[0]，确保当所有字符都不大于target时，直接返回数组第一个元素，满足循环特性要求。
2. 合并条件分支：把等于和小于target的情况合并处理，这两种场景都需要向右搜索更大的字符，无需单独处理等于的情况（避免错误将target设为结果）。
3. 精准更新结果：仅当找到大于target的字符时才更新res，同时向左缩小搜索范围，确保最终得到的是最小的符合要求的字符。

内容的提问来源于stack exchange，提问作者user19591368