题目描述
思路解析
一句话答案：LeetCode 744 寻找比目标字母大的最小字母：升序字母表里找第一个严格大于 target 的位置，靠左闭右开二分砍半，收缩到越界就取模环形回首，时间 O(log n)、空间 O(1)。
升序字母表里，挑出比 target 大的最小那个
给一排升序（从小到大排好）的小写字母 letters 和目标 target，返回严格大于 target 的最小字母；一个都不比它大就绕回开头返回 letters[0]。题面 ['c','f','j']：target='a' 答案 'c'；target='j' 环形回 'c'。题目还卡死 O(log n)。
逐个字母往后比，为什么配不上 O(log n)
从头往后逐个和 target 比，遇到第一个更大的就停。n 个字母最坏要比满 n 次，是 O(n)。字母表顶多 26 个不多，可换到几十万长的升序数组就卡死，O(log n) 正是要堵掉逐个比。
字母表排好序，半排可以一次跳过
钥匙在『升序』。挨个位置问『这字母严格大于 target 吗』，答案一定前一串否、后一串是：某字母超过 target 后右边全超过。要找从否到是的分界后第一个是。看中点，不大于 target 连左边一起丢，大于就右半不看、它自己留候选。
普通二分撞到相等就返回，这里相等不算数：'j' 不比 'j' 大得跳过。所以只分两支：≤ target 往右扔、> target 收进候选，即库函数 upper_bound（第一个严格大于目标的位置）。
中点比完，左界右界各挪到哪
用左闭右开区间 [left, right) 框住待查位置。起手 left=0、right=n（n 不是 n-1，给越界回首留落点）。每轮 mid=(left+right)//2 看 letters[mid]：≤ target 就 left=mid+1；> target 时 mid 可能是答案、不能扔，right=mid 往左继续找。收空时 left 停在第一个是。
整排都不比 target 大时 left 涨到 n，返回 letters[left % n]：取模把 n 变回 0、绕回 letters[0]，省掉 if。
['c','f','j'] 找 'a'、找 'j' 各走几轮
先找 'a'。left=0、right=3，mid=1，'f' ≤ 'a' 不成立，right 收到 1。第二轮 mid=0，'c' ≤ 'a' 也不成立，right 收到 0。left=right=0 收空，返回 letters[0 % 3]='c'。
再看 target='j'（触发环形）。mid=1，'f' ≤ 'j' 成立，left 跳到 2。第二轮 mid=2，'j' ≤ 'j' 相等也算 ≤，left 跳到 3。收空，left=3=n，返回 letters[3 % 3]='c'，取模绕回开头。
收完 left 可能正好等于 n，直接读就越界
每比一次区间减半，最多 log₂n 轮，时间 O(log n)；只动 left、right 两个下标，空间 O(1)。
判断丢等号写成 letters[mid] < target，相等的字母混进候选。收缩后 left 可能等于 n，直接 letters[left] 会越界，靠 letters[left % n] 绕回 0。左闭右开配 left=mid+1 / right=mid，抄双闭 right=mid-1 会漏格或死循环。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住「找第一个大于 target 的位置：不大于就 left=mid+1；大于就把 mid 记成候选、right=mid 往左继续找」，下面每帧都在套它。
开始二分:区间用左闭右开 [0, 8) 表示。一旦遇到比 'a' 大的字母,就把它记成「当前可行候选」标绿、再继续往它左边找更小的;灰格是已彻底排除、不再搜的范围。
当前搜索区间 [0, 8) 的正中间是 letters[4]='p'。它严格大于 'a',它会成为新的、更靠左的可行候选。
letters[4]='p' 比 'a' 大,把它记成新的、更靠左的可行候选(绿色移到下标 4);只把它右边灰掉。接着到它左边找有没有更小的、也合格的位置。
当前搜索区间 [0, 4) 的正中间是 letters[2]='j'。它严格大于 'a',它会成为新的、更靠左的可行候选。绿色那格是目前记下的可行候选。
letters[2]='j' 比 'a' 大,把它记成新的、更靠左的可行候选(绿色移到下标 2);只把它右边灰掉。接着到它左边找有没有更小的、也合格的位置。
当前搜索区间 [0, 2) 的正中间是 letters[1]='f'。它严格大于 'a',它会成为新的、更靠左的可行候选。绿色那格是目前记下的可行候选。
letters[1]='f' 比 'a' 大,把它记成新的、更靠左的可行候选(绿色移到下标 1);只把它右边灰掉。接着到它左边找有没有更小的、也合格的位置。
当前搜索区间 [0, 1) 的正中间是 letters[0]='c'。它严格大于 'a',它会成为新的、更靠左的可行候选。绿色那格是目前记下的可行候选。
letters[0]='c' 比 'a' 大,把它记成新的、更靠左的可行候选(绿色移到下标 0);只把它右边灰掉。此时区间 [0, 0) 收空,保留的候选下标 0('c')就是答案。
二分结束,left 停在 0,letters[0]='c' 就是第一个严格大于 'a' 的字母(绿色),即答案。
开始二分:区间用左闭右开 [0, 8) 表示。一旦遇到比 'm' 大的字母,就把它记成「当前可行候选」标绿、再继续往它左边找更小的;灰格是已彻底排除、不再搜的范围。
当前搜索区间 [0, 8) 的正中间是 letters[4]='p'。它严格大于 'm',它会成为新的、更靠左的可行候选。
letters[4]='p' 比 'm' 大,把它记成新的、更靠左的可行候选(绿色移到下标 4);只把它右边灰掉。接着到它左边找有没有更小的、也合格的位置。
当前搜索区间 [0, 4) 的正中间是 letters[2]='j'。它不大于(≤) 'm',它和它左边都不可能是答案,答案在它右边。绿色那格是目前记下的可行候选。
letters[2] 不大于 'm',把 mid 及它左边整段灰掉排除,left 收到 3。绿色候选不动,继续在它左边找更小的。
当前搜索区间 [3, 4) 的正中间是 letters[3]='m'。它不大于(≤) 'm',它和它左边都不可能是答案,答案在它右边。绿色那格是目前记下的可行候选。
letters[3] 不大于 'm',把 mid 及它左边整段灰掉排除,left 收到 4。区间 [4, 4) 收空,保留的候选下标 4('p')就是答案。
二分结束,left 停在 4,letters[4]='p' 就是第一个严格大于 'm' 的字母(绿色),即答案。
开始二分:区间用左闭右开 [0, 8) 表示。一旦遇到比 'z' 大的字母,就把它记成「当前可行候选」标绿、再继续往它左边找更小的;灰格是已彻底排除、不再搜的范围。
当前搜索区间 [0, 8) 的正中间是 letters[4]='p'。它不大于(≤) 'z',它和它左边都不可能是答案,答案在它右边。
letters[4] 不大于 'z',把 mid 及它左边整段灰掉排除,left 收到 5。区间每次砍一半。
当前搜索区间 [5, 8) 的正中间是 letters[6]='t'。它不大于(≤) 'z',它和它左边都不可能是答案,答案在它右边。
letters[6] 不大于 'z',把 mid 及它左边整段灰掉排除,left 收到 7。区间每次砍一半。
当前搜索区间 [7, 8) 的正中间是 letters[7]='x'。它不大于(≤) 'z',它和它左边都不可能是答案,答案在它右边。
letters[7] 不大于 'z',把 mid 及它左边整段灰掉排除,left 收到 8。区间收空且没有候选,说明没有比 'z' 大的,稍后环形回 letters[0]。
二分结束 left=8 等于数组长度——说明没有字母比 'z' 大,按环形规则回到开头,答案是 letters[0]='c'(绿色)。
边界先想清：相等要跳过；无更大者(target≥末位)靠环形回 letters[0]；单元素无需特判，它比 target 大就直接返回、否则才环形。
认出「找第一个满足条件的位置」这个母题，二分就不再靠背模板。
参考代码
from typing import Listclass Solution: def nextGreatestLetter(self, letters: List[str], target: str) -> str: left, right = 0, len(letters) while left < right: mid = (left + right) // 2 if letters[mid] <= target: left = mid + 1 else: right = mid return letters[left % len(letters)]复杂度
- 时间：O(log n)，每次范围减半
- 空间：O(1)，只用 left、right 两个下标
易错点
面试追问把动画讲成自己的话
追问这其实是哪一类二分？
追问为什么用左闭右开而不是双闭区间？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
两个数组间的距离值
LeetCode 1385 · 简单 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题