边界问题

写二分查找时，我们经常先看到这样的初始化： left = 0 right = len(nums) - 1 本文讨论的输入是按非递减顺序排列、允许重复值的 list[int]。精确查找要返回某个等于 target 的实际下标，不存在时返回 -1；左边界查找要返回 [0, n] 中第一个满足 nums[i] >= target 的位置，如果不存在这样的数组元素，就返回 n。 它看起来像是在声明一个闭区间，但只看这两行还不够。真正决定区间含义的是下面四件事是否一致： left 和 right 是候选下标、未分类边界，还是哨兵； 循环在什么条件下说明仍有实际元素需要检查； 检查 mid 后，更新是否正确排除了它； 循环结束时，哪个位置承载最终答案。 最可靠的判断方法不是背代码，而是先问一句： 当前哪些实际下标还没有被排除或分类，答案位置又被限制在哪个范围内？ 这些持续成立的事实就是二分查找的循环不变式。区间符号、初始化和更新规则都应该从它推出来。 闭区间 [left, right] 当 left 和 right 都指向尚未排除的实际数组下标时，候选集合是闭区间： left = 0 right = len(nums) - 1 此时两个端点都可能是答案，所以只要 left <= right，区间就仍然非空： while left <= right: 如果 mid 不是答案，下一轮必须把它排除： if nums[mid] < target: left = mid + 1 else: right = mid - 1 因此，这套约定是： 项目 规则 候选集合 [left, right] 初始化 left = 0, right = n - 1 非空条件 left <= right 排除 mid left = mid + 1 或 right = mid - 1 空区间 left > right 它很适合“找到任意一个等于 target 的位置”：命中时直接返回，区间为空时返回不存在。 ...

副标题 / 摘要 这道题看似只是“找一个比目标大的字母”，本质上是经典的上界二分（upper_bound）问题：在有序字符数组中找到第一个 > target 的元素，并在找不到时从头环绕。本文给出完整的二分模板和多语言实现，帮你稳拿这类边界题。 预计阅读时长：8~10 分钟 适用场景标签：二分查找进阶、字符数组、上界查找 SEO 关键词：find smallest letter greater than target, upper_bound, 二分查找字符数组 目标读者与背景 目标读者 已经掌握基本二分查找，想进一步熟悉上下界（upper/lower bound）的同学； 在工程中需要在有序集合中找到“下一个更大值”的开发者； 准备中高级面试，想通过一道题统一上界二分写法的工程师。 背景 / 动机 很多系统都会用到“环形有序列表”的概念： 比如按字母排序的标签、按时间排序的分片； 想要找“比当前值更大的下一个值”，找不到就从头开始。 这道题「Find Smallest Letter Greater Than Target」正是这种模式的简化版，是练习上界二分的好题。 A — Algorithm（题目与算法） 题目重述 给定一个按非降序排序的字符数组 letters，数组中的字母都是小写英文字母。 给定一个字符 target，请你找到数组中严格大于 target 的最小字母并返回。 注意：letters 数组是环绕的——如果不存在这样的字母，则返回数组的第一个元素。 输入 letters: 排序好的小写字母数组，长度为 n，且 letters 中至少有两个不同的字母； target: 一个小写字母。 输出 字符：数组中比 target 大的最小字母；若不存在，则为 letters[0]。 示例 1 letters = ['c', 'f', 'j'] target = 'a' 所有比 'a' 大的字母有 ['c', 'f', 'j']； 其中最小的是 'c'。 输出：'c' ...