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"

 

Note:

1. letters has a length in range [2, 10000].
2. letters consists of lowercase letters, and contains at least 2 unique letters.
3. target is a lowercase letter.

 

二分查找，找到大于给定目标的列表中最小的元素。

 

C++(19ms):

1 class Solution { 2 public: 3     char nextGreatestLetter(vector
     
      & letters, char target) { 4         int left = 0 ; 5         int right = letters.size()-1 ; 6         while(left < right){ 7             int mid = left + (right-left)/2 ; 8             if (target < letters[mid]) 9                 right = mid ;10             else11                 left = mid + 1 ;12         }13         if (target < letters[left])14             return letters[left] ;15         else16             return letters[0] ;17     }18 };