# LeetCode 744. Find Smallest Letter Greater Than Target
[744. Find Smallest Letter Greater Than Target]([leetcode_url](https://leetcode.com/problems/find-smallest-letter-greater-than-target/description/)) (<font color=#00AF9B>Easy</font> 51.8%)

<!--
(<font color=#00AF9B>Easy</font> 53.8%)
(<font color=#FFB800>Medium</font> 39.6%)
(<font color=#FF375F>Hard</font>)
-->

- 限制 :
> 2 <= letters.length <= $10^4$

> letters[i] is a lowercase English letter.

> letters is sorted in non-decreasing order.

> letters contains at least two different characters.

> target is a lowercase English letter.

- Solution
煩人的邊界處理完之後，就是一般的 binary search。

- 時間複雜度: $O(lgn)$
- 空間複雜度: $O(1)$

- 程式碼

    class Solution {
    public:
        char nextGreatestLetter(vector<char>& letters, char target) {

            int left_index = 0, right_index = letters.size() - 1, mid_index;
            while(left_index <= right_index)
            {
                mid_index = (right_index - left_index)/ 2 + left_index;
                if(letters[mid_index] <= target)
                {
                    if(mid_index + 1 < letters.size() && letters[mid_index + 1] > target) return letters[mid_index + 1];
                    left_index = mid_index + 1;
                }
                else if(letters[mid_index] > target) right_index = mid_index - 1;
            }
            return letters[0];
        }
    };

</details>