Find Smallest Letter Greater Than Target

1. Problem Description

Given a sorted list of characters letters containing only lowercase English letters, and a target letter target, find the smallest letter in this ordered list that is greater than the target letter.

When comparing, the letters wrap around in order. For example:

If target = ‘z’ and letters = [‘a’, ‘b’], return ‘a’.

2. Approach

Similar to Binary Search Upper Bound

3. Implementation

func nextGreatestLetter(letters []byte, target byte) byte {
    if letters[len(letters)-1] <= target {
        return letters[0]
    }
    left := 0
    right := len(letters)-1
    for left < right {
        mid := left + (right-left)/2
        if letters[mid] < target {
            left = mid+1
        } else if letters[mid] > target {
            right = mid
        }else {
            left = mid+1
        }
    }
    return letters[left]
}

4. References

• 744. Find Smallest Letter Greater Than Target - LeetCode