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

朱雀 2023-10-05 13:23 72阅读 0赞

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

*  题目
 *  解题思路
 *  代码

## 题目 ##

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

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

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

**提示：**

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70_pic_center]

## 解题思路 ##

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

*  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];
            }
    
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20201109221502124.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70#pic_center