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返回下标2public 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) / 2m l (h - l) / 2当l h的结果大于整型能够表示的范围时(l h) / 2会发生加法溢出。而l和h在下标语境中均为正数h - l不会溢出因此最好使用第二种写法l (h - l) / 2。原文档 6 道题目中的所有实现均采用了这种防溢出写法。1.2 未成功查找的返回值循环退出时如果仍然没有查找到 key表示查找失败。原文档给出了两种可选的返回值语义返回-1以错误码表示没有查找到 key上面标准模板采用这种语义返回ll是 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 - 1h m循环条件l hl h返回值找到返回 m否则 -1始终返回l这三处是联动的原因如下为什么是h m在nums[m] key的情况下最左 key 位于[l, m]闭区间中m 位置本身也可能是解因此h只能取m而不能取m - 1。为什么循环条件必须是l h当h m时若循环条件仍写l h当m l h时会出现循环无法退出的死循环。原文档用下面这个示例演示了死循环过程nums {0, 1, 2}, key 1nums {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 ...为什么不能返回 -1循环退出时并不表示没有查找到 key所以不能把返回值当作错误码。调用方需要自行判断返回位置上取值nums[l]是否等于 key 来验证是否命中。记住一条总原则h的赋值表达式和循环条件必须成对选择——h m - 1配l hh 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 hh m - 1的配对循环退出后l恰好落在第一个大于 target 的元素的位置上当 target 比所有字符都大如示例中 target k时l n返回letters[0]完成回绕。4. 题目 3有序数组的 Single Element540. Single Element in a Sorted Array, MediumInput: [1, 1, 2, 3, 3, 4, 4, 8, 8] Output: 2题目描述一个有序数组中只有一个数不出现两次其余数各出现两次找出这个数。要求 O(log N) 时间复杂度因此不能直接遍历后异或那是 O(N)。解题思路设 index 为 Single Element 在数组中的位置。在 index 之前数组保持成对状态在 index 之后成对状态被破坏。由此可推导出判断规则m 取偶数位时若m 1 indexm 还在成对区则nums[m] nums[m 1]若m 1 indexm 已进入破坏区则nums[m] ! nums[m 1]。于是nums[m] nums[m 1]时 index 落在[m 2, h]令l m 2nums[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]; }两个实现要点m--的对齐技巧由于比较对象是nums[m]与nums[m1]这一对必须保证 m 始终为偶数下标即对的第一个元素否则判断会错位。原文档用if (m % 2 1) m--;保证 l/h/m 都在偶数位使查找区间大小始终为奇数最终区间收敛到单个元素。循环条件因为出现了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, MediumInput: [3,4,5,1,2] Output: 1解题思路把旋转数组从中间对半分必然得到一个包含最小元素的旋转数组 一个非递减数组且新旋转数组长度只有原来的一半因此可以折半逼近最小值时间复杂度 O(log N)。判断哪一半是旋转数组的依据是非递减数组的第一个元素 最后一个元素反之旋转数组必然nums[0] nums[len-1]。修改二分查找的判定条件l 代表 lowm 代表 midh 代表 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 ArrayInput: 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 - 1l hlen - 1命中 m否则 -1最左位置变型第一个 keynums[m] keyh ml hlenl需回查验证69 求开方最大mid x/midmid与x/mid比较h m - 1l hxh744 最小更大字符第一个 target二分后由l给出h m - 1l hn - 1l越界回绕letters[0]540 Single Element奇偶配对破坏点nums[m]与nums[m1]h ml hlen - 1nums[l]278 第一个错误版本第一个 badisBadVersion(mid)h midl hnl153 旋转数组最小值最小元素nums[m] nums[h]h ml hlen - 1nums[l]34 查找区间首/末位置findFirst(target)/findFirst(target1)-1h ml hlenl需回查验证核心结论可以浓缩为一句话先确定答案在h m还是h m - 1的区间里再据此确定循环条件最后根据退出时 l/h 的相对位置决定取 l 还是 h必要时在h初值上扩展到nums.length以覆盖插入到数组尾部之后的位置。掌握了这条推导链绝大多数二分变型题都能从模板现场推出来而不是靠背代码。本文内容源自 notes/Leetcode 题解 - 二分查找交叉参考了 notes/Leetcode 题解 - 目录该文档属于 Leetcode 题解系列中算法思想板块、11. 旋转数组的最小数字 与 53. 数字在排序数组中出现的次数。题号与难度69/744/540/278/153/34Easy/Medium以原文档标注为准。【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考