744.寻找比目标字母大的最小字母（二分查找）

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

• 题目
• 解题思路
• 代码

题目

给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。

在比较时，字母是依序循环出现的。举个例子：

• 如果目标字母 target = ‘z’ 并且字符列表为 letters = [‘a’, ‘b’]，则答案返回 ‘a’

提示：

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

解题思路

首先可以简单的给题目分为两种情况

• 1、target比char[]中的都大，这时候直接返回char[0]
• 2、char[]中有值大于target
• 如果有值大于target，那么我们就用二分查找法，缩小区间来找到该值。
• 首先left=0；right=char[].length-1; mid为(left+right)/2;
• 然后再进行遍历，如果有mid=target，那么要求的就是mid+1（char[]中大于target的最小值）；

代码

class Solution {
 public static char nextGreatestLetter(char[] letters, char target) {
        int left = 0;
        int right = letters.length - 1;

        if (target >= letters[letters.length - 1]) {//循环比较的处理
            return letters[0];
        } else {
            while (left < right) {//之所以不用<=是为了防止出现left=0，right=0，的情况，如果出现了那么  mid=(0+0)/2明显有错误。
                int mid = (left + right) / 2;
                if (letters[mid] <= target) {
                    left = mid + 1;
                }

                /*
                本来right应该等于mid-1，但是也是为了防止出现left=right=0的情况，如果出现会导致少循环一次，进而导致错误
                例如：char["c","f","j"] target="c"
                如果right=mid-1，输出"c"（错误），
                如果right=mid，输出”f“（正确）
                 */
                if (letters[mid] > target) {
                    right = mid;
                }
            }
            return letters[left];
        }

    }
}