二分搜索（七）744. 寻找比目标字母大的最小字母 二分搜索基本题型

744. 寻找比目标字母大的最小字母

给你一个字符数组letters，该数组按非递减顺序排序，以及一个字符target。letters里至少有两个不同的字符。

返回letters中大于target的最小的字符。如果不存在这样的字符，则返回letters的第一个字符。

示例 1：

输入:letters = ['c', 'f', 'j']，target = 'a'输出:'c'解释：letters 中字典上比 'a' 大的最小字符是 'c'。

示例 2:

输入:letters = ['c','f','j'], target = 'c'输出:'f'解释：letters 中字典顺序上大于 'c' 的最小字符是 'f'。

示例 3:

输入:letters = ['x','x','y','y'], target = 'z'输出:'x'解释：letters 中没有一个字符在字典上大于 'z'，所以我们返回 letters[0]。

class Solution { public: char nextGreatestLetter(vector<char>& letters, char target) { int left = 0, right = letters.size()-1; char res = letters[0]; while(left <= right) { int mid = left + ((right - left) / 2); if(letters[mid] == target) { // 当目标就是mid值的时候 left = mid + 1; // 但我要的是比mid大的值，所以你去右区间找吧 } else if(letters[mid] > target) { // mid值大于目标值 res = letters[mid];// 我要的就是大于的值，先保存一下 right = mid - 1;// 你再去左区间看看，有没有比现在保存的更小的大值 } else { left = mid + 1;// mid值小于目标值，直接继续去右区间找吧 } } return res; } };