LeetCode 寻找比目标字母大的最小字母（二分搜索）

问题描述：

给定一个只包含小写字母的有序数组letters 和一个目标字母 target，寻找有序数组里面比目标字母大的最小字母。
数组里字母的顺序是$\color{red}{循环}$循环的。举个例子，如果目标字母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"
输入:
letters = ["c", "f", "j"]
target = "g"
输出: "j"
输入:
letters = ["c", "f", "j"]
target = "j"
输出: "c"
输入:
letters = ["c", "f", "j"]
target = "k"
输出: "c"

注:

letters长度范围在[2, 10000]区间内。
letters 仅由小写字母组成，最少包含两个不同的字母。
目标字母target 是一个小写字母。

思路分析：

看到$\color{red}{有序}$有序二字，我们的第一反应就应该是“二分搜索”，没错这道就是利用二分搜索。首先我们需要知道什么时候需要进行循环，只有当target >= target.back()的时候需要循环。

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        //二分搜索的三个指针
        int left = 0, right = letters.size() - 1, mid;
        while (left < right){
            int mid = (left + right) / 2;
            if (letters[mid] <= target){
                //因为letters有序，如果letters[mid] <= target，则[left, mid] < target
                //即比目标字母大的字母必定不会出现在[left, mid]
                left = mid + 1;
            }
            else{
                //否则结果必定在[left, mid]中
                right = mid;
            }
        }
        if (target >= letters[left]){
            //注意如果left == letters.size() - 1时，这时需要判断结果是否需要进行循环
            left = 0;
        }
        return letters[left];
    }
};

其实我们可以先判断是否需要循环处理。

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
         if (target >= letters.back()){
            //只有当搜索的字母不小于letters中最大的字母时需要循环
            return letters[0];
        }
        //二分搜索的三个指针
        int left = 0, right = letters.size() - 1, mid;
        while (left < right){
            int mid = (left + right) / 2;
            if (letters[mid] <= target){
                //因为letters有序，如果letters[mid] <= target，则[left, mid] < target
                //即比目标字母大的字母必定不会出现在[left, mid]
                left = mid + 1;
            }
            else{
                //否则结果必定在[left, mid]中
                right = mid;
            }
        }
        return letters[left];
    }
};