744. Find Smallest Letter Greater Than Target

问题：

给定一个升序字符数组。

求比给定target字符大的，最小的字符。（假设给定字符数组是循环的，即第一个字符>最后一个字符）

Examples:
Input:
letters = ["c", "f", "j"]
target = "a"
Output: "c"

Input:
letters = ["c", "f", "j"]
target = "c"
Output: "f"

Input:
letters = ["c", "f", "j"]
target = "d"
Output: "f"

Input:
letters = ["c", "f", "j"]
target = "g"
Output: "j"

Input:
letters = ["c", "f", "j"]
target = "j"
Output: "c"

Input:
letters = ["c", "f", "j"]
target = "k"
Output: "c"

Note:
letters has a length in range [2, 10000].
letters consists of lowercase letters, and contains at least 2 unique letters.
target is a lowercase letter.

　　

解法：二分查找(Binary Search)

在给定字符数组letters中，找到第一个>target字符的字符。

⚠️ 注意：（字符数组是循环：）若未找到，则返回letters[0]

代码参考：

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int l = 0, r = letters.size();
        while(l<r) {
            int m = l+(r-l)/2;
            if(letters[m]>target) {//找到第一个>target
                r = m;
            } else {
                l = m+1;
            }
        }
        return (l==letters.size())?letters[0]:letters[l];
    }
};