［抄题］：

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"

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

Input:

letters = ["c", "f", "j"]

target = "k"

Output: "c"
结果是最后一位，但是需要返回第一位 结果%n （看余数 不止看倍数）

［思维问题］：

“第一个最大”居然没看出来是二分查找问题。字母换成index数字后继续操作啊

［一句话思路］：

［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

“第一个最大”居然没看出来是二分查找问题。字母换成index数字后继续操作啊

［复杂度］：Time complexity: O(lgn) Space complexity: O(1)

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［关键模板化代码］：

九章的不行就用这一套：

while (lo < hi)

lo = mid + 1

//Terminal condition is 'lo < hi', to avoid infinite loop when target is smaller than the first element

        while (lo < hi) {

            int mid = lo + (hi - lo) / 2;

            if (a[mid] > x)     hi = mid;

            else    lo = mid + 1;                 //a[mid] <= x

        }

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

class Solution {

    public char nextGreatestLetter(char[] letters, char target) {

        //ini

        int n = letters.length;

        int start = 0, end = n;

        //bs

        while (start < end) {

            int mid = start + (end - start) / 2;

            if (target < letters[mid]) {

                end = mid;

            }else {

                start = mid + 1;

            }

        }

        //return

        return letters[start % n];

    }

}