LeetCode : 744. Find Smallest Letter Greater Than Target 二分查找，比目标值大的最小元素

我不是女神ヾ 2021-06-24 16:10 336阅读 0赞

**试题**  
Given a list of sorted characters letters containing only lowercase letters, and given a target letter target, find the smallest element in the list that is larger than the given target.

Letters also wrap around. For example, if the target is target = ‘z’ and letters = \[‘a’, ‘b’\], the answer is ‘a’.

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”  
**代码**  
1、如果等于的话有两种可能：一是正好右边就是最小元素，此时left+1刚好，另外就是右边元素是target的重复值，此时left+1相当于区间的更新。  
2、如果target大于mid，直接更新区间即可  
3、如果target小于mid，一种极端情况就是此时mid刚好是最小元素，区间更新后最小元素将会出现在区间之外，这时候循环终止条件必须有等于才能使得left+1能够定位到最小元素。

class Solution {
        public char nextGreatestLetter(char[] letters, char target) {
            int left=0, right=letters.length-1;
            while(left<=right){
                int mid = left+(right-left)/2;
                if(letters[mid]==target){
                    left = mid+1;
                }else if(letters[mid]>target){
                    right = mid-1;
                }else if(letters[mid]<target){
                    left = mid+1;
                }
            }
            return left<letters.length?letters[left]:letters[0];
            
        }
    }