744 Find Smallest Letter Greater Than Target

Leetcodt

Given a characters array letters that is sorted in non-decreasing order and a character target, return the smallest character in the array that is larger than target.

Note that the letters wrap around.

For example, if target == 'z' and letters == ['a', 'b'], the answer is 'a'.

Example 1:

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

Example 2:

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

Example 3:

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

左闭右开的二分查找。如果左指针为数组长度，说明没有找到，返回第一个元素。

public char nextGreatestLetter(char[] letters, char target) {
    int low=0,high=letters.length;
    int mid;
    char c;
    while(low<high){
        mid=(low+high)/2;
        c=letters[mid];
        if(c<=target){
            low=mid+1;
        } else {
            high=mid;
        }
    }
    return low==letters.length?letters[0]:letters[low];
}