LeetCode 744. 寻找比目标字母大的最小字母（二分查找）

Problem: 744. 寻找比目标字母大的最小字母

1. 整体思路

核心问题

在有序字符数组 letters 中，找到第一个严格大于target 的字符。如果不存在，返回 letters[0]。

算法逻辑

利用数组已经排序的特性，使用二分查找来将时间复杂度从 O(N) 降低到 O(log N)。

1. 区间定义：
   • 使用左闭右开区间 [left, right)。
   • left = 0, right = n (数组长度)。
   • 这种定义下，left 最终会指向我们要找的目标位置。
2. 二分逻辑：
   • 计算中点 mid。
   • 比较：
     • 如果 letters[mid] <= target：说明 mid 及左边的元素都不符合条件（我们需要找严格大于的），或者 mid 处的值太小了。因此，目标一定在 mid 的右侧。更新 left = mid + 1。
     • 如果 letters[mid] > target：说明 mid 可能是目标，或者目标在 mid 的左侧（更小的符合条件的字符）。更新 right = mid。
   • 循环结束：当 left == right 时，left（或 right）指向的就是数组中第一个大于 target 的元素的位置。
3. 结果处理：
   • 如果找到的位置 right 依然在数组范围内（right < n），说明找到了。
   • 如果 right == n，说明数组中所有元素都 ≤ target，根据题目循环要求，返回 letters[0]。

2. 完整代码

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int n = letters.length;
        // 定义二分查找的边界
        
        
           ;
           n;
        
         (left < right) {
            
               left + (right - left) / ;
            
            
            
             (letters[mid] <= target) {
                left = mid + ;
            }
            
            
            
             {
                right = mid;
            }
        }
        
        
        
        
         right < n ? letters[right] : letters[];
    }
}