題目網址：https://leetcode.cn/problems/find-smallest-letter-greater-than-target/

題意：給一 sorted char array letters, 在其中找到比 target 大的最小 char。

注意：letters 是循環的

  • e.g. target == 'z' 且 letters == ['a', 'b'], 則返回 'a'

Solution：

想法：利用 binary search

  • letters[mid] > target 時, 往左查找, 看是否有比 mid 更小的
  • letters[mid] <= target 時, 往右查找

最後記得檢查是否 > target, 如果不滿足(代表 letters 中沒有 > target 的 char), 則返回 letters[0]

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int left = 0, right = letters.size() - 1;

        while (left < right) {
            const int mid = left + (right - left) / 2; // 避免 overflow

            if (letters[mid] > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return letters[left] > target ? letters[left] : letters[0];
    }
};
  • time：$O(log(n))$ ➔ Binary Search
  • space：$O(1)$ ➔ 只需常數空間