the.forgotten

leetcode地址：

https://leetcode.com/problems/find-smallest-letter-greater-than-target/description/

難度：easy

描述：

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.

簡單翻譯一下：

給定一個有序的字符數組 letters 和一個字符 target，要求找出 letters 中大于 target 的最小字符，如果找不到就返回第 1 個字符。

這道題可以用遍歷法，但是如果向讓時間復雜度更小，可以用二分法，時間復雜度為O(logN)。就這道題而言本身并不難，二分法只要注意一下邊界條件。但是從這個題目里，我們可以提煉出一個比較通用的應用場景，即在一個有序的數組中（不一定是字母或者數字），有序意味著元素按照某種屬性遞增排列（遞減的情況是等價的），屬性相同的元素一定是相鄰的，這時，我們在這個數組中找出屬性滿足特定條件的最小元素，或最大元素，這兩類問題都可以用二分法的變種來實現。下面分為兩種情況：

1. 求滿足特定條件的最小元素，我們假設數組是遞增的，也就是求最靠近左邊的元素。對于這種問題，我們在每次對中間元素進行判斷時（假設中間下標是m），首先判斷中間元素是否大于或者等于（注意這里等于也算在內），如果是，那么將上界調整為中間下標m，否則將下屆調整為m+1。這里計算m的方法為m=（l+h）/2;

2. 求滿足特定條件的最大元素，也就是求最靠近右邊的元素，這時我們需要將區間不斷往右邊逼近。判斷中間元素是否小于或者等于目標值，如果是，將下屆調整為m，否則將上界調整為m-1。計算m的方法為m=（l+h+1）/2。這里有個很隱蔽的邊界問題，如果m的計算方法仍然使用m=（l+h）/2，那么當h-l==1時，此時的m=l，這時如果中間元素等于目標值，那么就會形成死循環，因為此時中間下標和下屆是相同的，所以下屆得不到調整，形成死循環。