CS-Notes Leetcode 题解：二分查找的标准模板、边界规则与 6 道经典变型题

CS-Notes Leetcode 题解：二分查找的标准模板、边界规则与 6 道经典变型题

【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes

本文基于 notes/Leetcode 题解 - 二分查找 整理。文章先给出二分查找的标准模板，并逐一拆解最容易出错的三处细节——中值 m 的防溢出计算、h = m时循环条件的选择、未命中时的返回值语义；再完整收录原文档的 6 道经典 Leetcode 题目（求开方、查找插入位置、有序数组 Single Element、第一个错误的版本、旋转数组最小值、查找区间）的解题思路与 Java 实现，并结合 11. 旋转数组的最小数字、53. 数字在排序数组中出现的次数 两篇同仓库题解交叉印证。读完本文，你可以掌握一个"可推导、可复用"的二分模板，并理解为什么不同题目中h = m/h = m - 1、l < h/l <= h必须成对出现。

1. 标准二分查找模板

二分查找（Binary Search）也称折半查找：每次比较中值后都能将查找区间减半，这种折半特性决定了其时间复杂度为O(log N)。标准实现如下，对有序数组[1,2,3,4,5]查找key = 3返回下标2：

public int binarySearch(int[] nums, int key) { int l = 0, h = nums.length - 1; while (l <= h) { int m = l + (h - l) / 2; if (nums[m] == key) { return m; } else if (nums[m] > key) { h = m - 1; } else { l = m + 1; } } return -1; }

该模板有三个关键设计决策，下面逐一说明。

1.1 中值 m 的防溢出计算

计算中值 m 有两种方式：

• m = (l + h) / 2
• m = l + (h - l) / 2

当l + h的结果大于整型能够表示的范围时，(l + h) / 2会发生加法溢出。而l和h在下标语境中均为正数，h - l不会溢出，因此最好使用第二种写法l + (h - l) / 2。原文档 6 道题目中的所有实现均采用了这种防溢出写法。

1.2 未成功查找的返回值

循环退出时如果仍然没有查找到 key，表示查找失败。原文档给出了两种可选的返回值语义：

• 返回-1：以错误码表示没有查找到 key（上面标准模板采用这种语义）；
• 返回l：l是 key 插入 nums 中的正确位置，即"查找插入位置"语义（后文第 2 题、第 6 题均用到）。

1.3 变型模板：查找最左位置（闭区间h = m的写法）

二分查找有很多变型，实现变型时边界值的判断是核心。例如在含有重复元素的数组中查找 key 的最左位置：

public int binarySearch(int[] nums, int key) { int l = 0, h = nums.length; while (l < h) { int m = l + (h - l) / 2; if (nums[m] >= key) { h = m; } else { l = m + 1; } } return l; }

该实现与正常实现有三处不同：

项目	标准查找	最左位置变型
h的赋值	h = m - 1	h = m
循环条件	l <= h	l < h
返回值	找到返回 m，否则 -1	始终返回l

这三处是联动的，原因如下：

1. 为什么是h = m：在nums[m] >= key的情况下，最左 key 位于[l, m]闭区间中（m 位置本身也可能是解），因此h只能取m而不能取m - 1。
2. 为什么循环条件必须是l < h：当h = m时，若循环条件仍写l <= h，当m == l == h时会出现"循环无法退出"的死循环。原文档用下面这个示例演示了死循环过程（nums = {0, 1, 2}, key = 1）：

nums = {0, 1, 2}, key = 1 l m h 0 1 2 nums[m] >= key 0 0 1 nums[m] < key 1 1 1 nums[m] >= key 1 1 1 nums[m] >= key ...

3. 为什么不能返回 -1：循环退出时并不表示没有查找到 key，所以不能把返回值当作错误码。调用方需要自行判断返回位置上取值nums[l]是否等于 key 来验证是否命中。

记住一条总原则：h的赋值表达式和循环条件必须成对选择——h = m - 1配l <= h，h = m配l < h。后文所有题目都是这条原则的具体应用。

2. 题目 1：求开方（69. Sqrt(x), Easy）

给定非负整数 x，求其整数开方（小数部分截断）。

Input: 4 Output: 2 Input: 8 Output: 2 Explanation: The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will be truncated.

解题思路：x 的开方 sqrt 一定在0 ~ x之间，且满足sqrt == x / sqrt（用除法避免平方溢出），因此可以把它转化为在0 ~ x区间内查找"满足 mid <= x / mid 的最大 mid"的二分查找问题。

public int mySqrt(int x) { if (x <= 1) { return x; } int l = 1, h = x; while (l <= h) { int mid = l + (h - l) / 2; int sqrt = x / mid; if (sqrt == mid) { return mid; } else if (mid > sqrt) { h = mid - 1; } else { l = mid + 1; } } return h; }

这里有两个值得注意的细节：

• 为什么循环退出后返回h而不是l：以 x = 8 为例，真正的开方是 2.82842...，答案应取 2 而不是 3。当循环条件为l <= h时，循环退出的瞬间必然有h = l - 1，此时l是第一个"平方大于 x"的候选值（3），而h才是最后一个"平方不大于 x"的候选值（2），所以返回h。
• 用x / mid而不是mid * mid：直接平方可能溢出 int 范围，除法比较既安全又避免了溢出。

3. 题目 2：大于给定元素的最小元素（744. Find Smallest Letter Greater Than Target, Easy）

题目描述：给定有序字符数组 letters 和字符 target，找出 letters 中大于 target 的最小字符；如果找不到则返回第 1 个字符。

Input: letters = ["c", "f", "j"] target = "d" Output: "f" Input: letters = ["c", "f", "j"] target = "k" Output: "c"

解题思路：这是"查找插入位置"语义的直接应用——找到第一个> target的元素位置l；若l == n说明所有字符都不大于 target，按题意环形回绕到letters[0]。

public char nextGreatestLetter(char[] letters, char target) { int n = letters.length; int l = 0, h = n - 1; while (l <= h) { int m = l + (h - l) / 2; if (letters[m] <= target) { l = m + 1; } else { h = m - 1; } } return l < n ? letters[l] : letters[0]; }

注意这里使用的是l <= h+h = m - 1的配对：循环退出后l恰好落在"第一个大于 target 的元素"的位置上；当 target 比所有字符都大（如示例中 target = "k"）时l == n，返回letters[0]完成回绕。

4. 题目 3：有序数组的 Single Element（540. Single Element in a Sorted Array, Medium）

Input: [1, 1, 2, 3, 3, 4, 4, 8, 8] Output: 2

题目描述：一个有序数组中只有一个数不出现两次（其余数各出现两次），找出这个数。要求 O(log N) 时间复杂度，因此不能直接遍历后异或（那是 O(N)）。

解题思路：设 index 为 Single Element 在数组中的位置。在 index 之前，数组保持"成对"状态；在 index 之后，成对状态被破坏。由此可推导出判断规则（m 取偶数位时）：

• 若m + 1 < index（m 还在成对区），则nums[m] == nums[m + 1]；
• 若m + 1 >= index（m 已进入破坏区），则nums[m] != nums[m + 1]。

于是：nums[m] == nums[m + 1]时 index 落在[m + 2, h]，令l = m + 2；nums[m] != nums[m + 1]时 index 落在[l, m]，令h = m。

public int singleNonDuplicate(int[] nums) { int l = 0, h = nums.length - 1; while (l < h) { int m = l + (h - l) / 2; if (m % 2 == 1) { m--; // 保证 l/h/m 都在偶数位，使得查找区间大小一直都是奇数 } if (nums[m] == nums[m + 1]) { l = m + 2; } else { h = m; } } return nums[l]; }

两个实现要点：

1. m--的对齐技巧：由于比较对象是nums[m]与nums[m+1]这一"对"，必须保证 m 始终为偶数下标（即"对的第一个元素"），否则判断会错位。原文档用if (m % 2 == 1) m--;保证 l/h/m 都在偶数位，使查找区间大小始终为奇数，最终区间收敛到单个元素。
2. 循环条件：因为出现了h = m，按第 1 节的总原则，循环条件必须用l < h。

5. 题目 4：第一个错误的版本（278. First Bad Version, Easy）

题目描述：版本序列为[1, 2, ..., n]，从第 x 个版本开始出现错误，之后的版本全部错误。提供 APIisBadVersion(int x)查询某版本是否错误，要求找到第一个错误的版本。

解题思路：这是"最左位置变型"的教科书案例。若第 m 个版本已出错，则第一个错误版本在[l, m]之间，令h = m；否则在[m + 1, h]之间，令l = m + 1。

public int firstBadVersion(int n) { int l = 1, h = n; while (l < h) { int mid = l + (h - l) / 2; if (isBadVersion(mid)) { h = mid; } else { l = mid + 1; } } return l; }

因为h的赋值表达式为h = m，所以循环条件为l < h（若误写成l <= h，当l == h时会死循环）。循环退出时l == h，该位置即为第一个错误版本。此题与第 1 节的"最左位置变型"完全同构：把"数组值 >= key"替换为"版本已出错"即可。

6. 题目 5：旋转数组的最小数字（153. Find Minimum in Rotated Sorted Array, Medium）

Input: [3,4,5,1,2] Output: 1

解题思路：把旋转数组从中间对半分，必然得到"一个包含最小元素的旋转数组 + 一个非递减数组"，且新旋转数组长度只有原来的一半，因此可以折半逼近最小值，时间复杂度 O(log N)。判断哪一半是旋转数组的依据是：非递减数组的第一个元素 <= 最后一个元素（反之旋转数组必然nums[0] > nums[len-1]）。

修改二分查找的判定条件（l 代表 low，m 代表 mid，h 代表 high）：

• 当nums[m] <= nums[h]时，[m, h]区间是非递减数组，最小值就在其中，令h = m；
• 否则[m + 1, h]区间是旋转数组，最小值在其中，令l = m + 1。

public int findMin(int[] nums) { int l = 0, h = nums.length - 1; while (l < h) { int m = l + (h - l) / 2; if (nums[m] <= nums[h]) { h = m; } else { l = m + 1; } } return nums[l]; }

同样因为h = m，循环条件取l < h；退出时l == h即最小元素下标。

扩展：元素允许重复时的处理

本仓库的 11. 旋转数组的最小数字（剑指 Offer 版本，数组为非递减排序的旋转）讨论了元素可重复的情形：当nums[l] == nums[m] == nums[h]时（例如{1,1,1,0,1}），无法判断最小值在哪个区间，必须退化为 O(N) 的顺序查找兜底：

public int minNumberInRotateArray(int[] nums) { if (nums.length == 0) return 0; int l = 0, h = nums.length - 1; while (l < h) { int m = l + (h - l) / 2; if (nums[l] == nums[m] && nums[m] == nums[h]) return minNumber(nums, l, h); else if (nums[m] <= nums[h]) h = m; else l = m + 1; } return nums[l]; } private int minNumber(int[] nums, int l, int h) { for (int i = l; i < h; i++) if (nums[i] > nums[i + 1]) return nums[i + 1]; return nums[l]; }

顺序查找通过扫描相邻的"下降沿"（nums[i] > nums[i + 1]）定位最小值。这说明：当判定条件失去区分度时，二分必须准备一个线性兜底分支，这是二分变型在实际工程中常见的退化路径。

7. 题目 6：查找区间（34. Find First and Last Position of Element in Sorted Array）

Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4] Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]

题目描述：给定有序数组 nums 和目标值 target，找到 target 在 nums 中的第一个位置和最后一个位置（要求 O(log N)）。

解题思路：分别用两次二分找第一个位置和最后一个位置，但二者写法不同。原文档采用的技巧是：把"寻找 target 的最后一个位置"转换成"寻找 target + 1 的第一个位置"再往前移动一个位置，这样只需实现一个"找第一个 >= 值的位置"的二分查找：

public int[] searchRange(int[] nums, int target) { int first = findFirst(nums, target); int last = findFirst(nums, target + 1) - 1; if (first == nums.length || nums[first] != target) { return new int[]{-1, -1}; } else { return new int[]{first, Math.max(first, last)}; } } private int findFirst(int[] nums, int target) { int l = 0, h = nums.length; // 注意 h 的初始值 while (l < h) { int m = l + (h - l) / 2; if (nums[m] >= target) { h = m; } else { l = m + 1; } } return l; }

这里有一个极易踩的坑：h的初始值必须是nums.length而不是nums.length - 1。原文档用nums = [2,2], target = 2演示了后果：

• 若h取nums.length - 1 = 1，则last = findFirst(nums, target + 1) - 1 = 1 - 1 = 0，结果错误。
• 根本原因在于findFirst只会返回[0, nums.length - 1]范围内的值。而对于findFirst([2,2], 3)，我们期望返回 3 的插入位置——数组最后一个位置的"再往后一个"，即nums.length = 2。
• 因此必须把h的初始值取为nums.length，使返回区间扩大为[0, nums.length]，才能覆盖"target 大于 nums 最后一个元素"的边界情况。

命中判定nums[first] != target则呼应了第 1.3 节的结论：h = m风格的二分退出时不能靠返回值判断成败，必须回查位置上的值。

本仓库 53. 数字在排序数组中出现的次数 是同一思想的另一个应用：求出 target 的首末位置后，last - first + 1即出现次数，且对"未命中返回 0"的边界做了同样的显式判断（first == nums.length || nums[first] != K）。

8. 小结：二分变型速查表

把原文档 6 道题与模板讨论归纳成一张速查表，方便面试与代码复查时对照：

题目	目标语义	判定条件	h 赋值	循环条件	h 初值	退出后取谁
标准查找	精确命中	nums[m] == key三分支	h = m - 1	l <= h	len - 1	命中 m，否则 -1
最左位置变型	第一个>= key	nums[m] >= key	h = m	l < h	len	l（需回查验证）
69 求开方	最大mid <= x/mid	mid与x/mid比较	h = m - 1	l <= h	x	h
744 最小更大字符	第一个> target	二分后由l给出	h = m - 1	l <= h	n - 1	l（越界回绕letters[0]）
540 Single Element	奇偶配对破坏点	nums[m]与nums[m+1]	h = m	l < h	len - 1	nums[l]
278 第一个错误版本	第一个 bad	isBadVersion(mid)	h = mid	l < h	n	l
153 旋转数组最小值	最小元素	nums[m] <= nums[h]	h = m	l < h	len - 1	nums[l]
34 查找区间	首/末位置	findFirst(target)/findFirst(target+1)-1	h = m	l < h	len	l（需回查验证）

核心结论可以浓缩为一句话：先确定"答案在h = m还是h = m - 1的区间里"，再据此确定循环条件，最后根据退出时 l/h 的相对位置决定取 l 还是 h，必要时在h初值上扩展到nums.length以覆盖"插入到数组尾部之后"的位置。掌握了这条推导链，绝大多数二分变型题都能从模板现场推出来，而不是靠背代码。

本文内容源自 notes/Leetcode 题解 - 二分查找，交叉参考了 notes/Leetcode 题解 - 目录（该文档属于 Leetcode 题解系列中"算法思想"板块）、11. 旋转数组的最小数字 与 53. 数字在排序数组中出现的次数。题号与难度（69/744/540/278/153/34，Easy/Medium）以原文档标注为准。

【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes