Leetcode 744 - Find Smallest Letter Greater Than Target

Note:

  • Classic binary search to find the first element that is bigger than or equal to target.
  • Note that we don’t need to add 1 to mid.

Question:

Given a characters array letters that is sorted in non-decreasing order and a character target, return the smallest character in the array that is larger than target.

Note that the letters wrap around.

  • For example, if target == 'z' and letters == [‘a’, ‘b’]`, the answer is ‘a’.

Example:

1
2
Input: letters = ["c","f","j"], target = "a"
Output: "c"

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* @param {character[]} letters
* @param {character} target
* @return {character}
*/
var nextGreatestLetter = function(letters, target) {
let left = 0, right = letters.length - 1;
while (left < right) {
const mid = left + ((right - left) >> 1);
if (letters[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
if (letters[left] <= target) return letters[0];
return letters[left];
};