接上文，我们继续来分享第二种解题思路：
方法二：二分查找
利用列表有序的特点，可以使用二分查找降低时间复杂度。
首先比较目标字母和列表中的最后一个字母，当目标字母大于或等于列表中的最后一个字母时，答案是列表的首个字母。当目标字母小于列表中的最后一个字母时，列表中一定存在比目标字母大的字母，可以使用二分查找得到比目标字母大的最小字母。
初始时，二分查找的范围是整个列表的下标范围。每次比较当前下标处的字母和目标字母，如果当前下标处的字母大于目标字母，则在当前下标以及当前下标的左侧继续查找，否则在当前下标的右侧继续查找。
代码
Python3
class Solution: def nextGreatestLetter(self, letters: List[str], target: str) -> str: return letters[bisect_right(letters, target)] if target < letters[-1] else letters[0]Java
class Solution { public char nextGreatestLetter(char[] letters, char target) { int length = letters.length; if (target >= letters[length - 1]) { return letters[0]; } int low = 0, high = length - 1; while (low < high) { int mid = (high - low) / 2 + low; if (letters[mid] > target) { high = mid; } else { low = mid + 1; } } return letters[low]; } }C#
public class Solution { public char NextGreatestLetter(char[] letters, char target) { int length = letters.Length; if (target >= letters[length - 1]) { return letters[0]; } int low = 0, high = length - 1; while (low < high) { int mid = (high - low) / 2 + low; if (letters[mid] > target) { high = mid; } else { low = mid + 1; } } return letters[low]; } }C++
class Solution { public: char nextGreatestLetter(vector<char> &letters, char target) { return target < letters.back() ? *upper_bound(letters.begin(), letters.end() - 1, target) : letters[0]; } };C
char nextGreatestLetter(char* letters, int lettersSize, char target){ if (target >= letters[lettersSize - 1]) { return letters[0]; } int low = 0, high = lettersSize - 1; while (low < high) { int mid = (high - low) / 2 + low; if (letters[mid] > target) { high = mid; } else { low = mid + 1; } } return letters[low]; }JavaScript
var nextGreatestLetter = function(letters, target) { const length = letters.length; if (target >= letters[length - 1]) { return letters[0]; } let low = 0, high = length - 1; while (low < high) { const mid = Math.floor((high - low) / 2) + low; if (letters[mid] > target) { high = mid; } else { low = mid + 1; } } return letters[low]; };复杂度分析
- 时间复杂度：O(logn) ，其中 n 是列表 letters 的长度。二分查找的时间复杂度是 O(logn) 。
- 空间复杂度：O(1) 。
