算法之二分查找

目录核心思想算法定义核心本质二段性比必须有序更准确的表述时间复杂度⼆分查找easy在排序数组中查找元素的第⼀个和最后⼀个位置medium1.查找区间左端点处理细节求中点​编辑​编辑2.查找区间右端点处理细节求中点最后附上模板​编辑x的平⽅根easy搜索插⼊位置easy⼭峰数组的峰顶easy解法二分查找寻找峰值medium解法二分查找算法情况一nums[mid] nums[mid1]mid 处在下降趋势情况二nums[mid] nums[mid1]mid 处在上升趋势搜索旋转排序数组中的最⼩值medium解法二分查找0〜n-1中缺失的数字easy解法二分查找算法LCR 173. 点名 —— 四种 O(n) 解法详解解法一哈希表解法二直接遍历找结果解法三位运算异或 XOR解法四数学高斯求和公式四种解法对比总表核心思想一个生活例子猜数字游戏我心里想了一个 1~100 之间的数你来猜。你猜 50 → 我说大了你猜 25 → 我说小了你猜 37 → 我说大了你猜 31 → 我说对了你每次都猜中间值每次排除一半的可能性。这就是二分查找的核心思想。100 个数字最多猜 7 次就能猜中因为 2^7 128 100。而如果从头到尾一个一个猜最多要 100 次。算法定义在一个有序序列中每次取中间元素与目标值比较如果中间元素等于目标值则找到如果中间元素大于目标值则在左半部分继续查找如果中间元素小于目标值则在右半部分继续查找。重复此过程直到找到目标值或搜索区间为空。关键前提前提说明必须支持随机访问数组可以链表不行无法 O(1) 取中间元素具有二段性见下方详解核心本质二段性比必须有序更准确的表述很多教材说二分查找必须用于有序数组这个说法不准确。有序只是二分查找的充分条件不是必要条件。什么是二段性二段性是指存在一个判定条件 P使得数组被 P 分成两段连续的区间——一段满足 P一段不满足 P。这样每次取 mid 判断 P就能确定性地排除一半在另一半中继续查找。数组: [ F F F F T T T T ]↑ ↑Pfalse 的段 Ptrue 的段​取 mid 判断 P(mid)- P(mid) false → mid 在左段答案在右段 → 舍去左半- P(mid) true → mid 在右段答案在左段含 mid→ 舍去右半为什么有序只是充分条件因为有序数组天然具有二段性。在升序数组中找 target定义判定函数P(i) (nums[i] target)升序: [1, 3, 5, 7, 9, 11], target 6P: F F F T T T↑第一个 6 的位置 lower_bound因为数组有序 target的元素一定连续出现在右边 target的元素连续出现在左边自然形成两段。有序保证了二段性但二段性不一定需要有序。无序但有二段性的经典例子例子 1寻找峰值LeetCode 162nums [1, 2, 3, 1]​完全无序但定义 P(i) (nums[i] nums[i1])P: T T F F↑ ↑上升段(T) 下降段(F)​取 mid如果 P(mid)T → 右边有峰值 → 舍去左半如果 P(mid)F → 左边有峰值 → 舍去右半例子 2旋转排序数组找最小值LeetCode 153nums [4, 5, 6, 7, 0, 1, 2]​不是升序但定义 P(i) (nums[i] nums[right])P: T T T T F F F↑ ↑大于右端的段 小于等于右端的段​取 mid如果 P(mid)T → 最小值在 mid 右边 → 舍去左半如果 P(mid)F → 最小值在 mid 及左边 → 舍去右半例子 3山脉数组找峰顶LeetCode 852nums [0, 2, 4, 6, 5, 3, 1]​定义 P(i) (nums[i] nums[i1])P: T T T F F F↑ ↑上坡段(T) 下坡段(F)二段性 vs 有序性有序性二段性定义数组元素递增/递减存在判定函数 P 将数组分成两段连续区间关系有序 ⇒ 二段性充分不必要二段性是有序的推广适用范围仅有序数组有序数组 旋转数组 峰值 山脉 任何有二段性的数组识别方式看数组是否排序看能否找到一个判定条件把数组分成可行/不可行两段理解了二段性面对一道题时不要问数组有序吗而要问我能否找到一个判定条件使得每次取 mid 都能确定性地排除一半如果能就能用二分。这才是二分查找最本质的前提。时间复杂度操作时间复杂度查找O(log n)空间O(1)每次将搜索范围缩小一半n → n/2 → n/4 → ... → 1共 log₂n 步。⼆分查找easy704. 二分查找 - 力扣LeetCode最简单的二分查找在排序数组中查找元素的第⼀个和最后⼀个位置medium34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCode利用二段性找左右端点。分别对应target的begin和end位置1.查找区间左端点左端点里左边全是 target右边全是 target的.把数组分成了两部分处理细节1循环条件我们选择leftright而不是leftright.解释a.当直接有结果的时候也就是leftright的时候就已经得到了最终结果此时无需再进入循环判断b.当值全大于target的时候我们的right需要左移到与left相遇为止也就是上面第1步中的查找左端 里的第2中情况也就是leftright的时候就已经得到了最终结果此时无需再进入循环判断c.当值全小于target的时候我们的left需要右移到与right相遇为止也就是上面第1步中的查找左端 里的第1中情况也就是leftright的时候就已经得到了最终结果此时无需再进入循环判断总结一下二分查找是非常容易写出死循环代码的所以我们要把控好细节问题比如a情况假如我们进入了循环且循环条件错误的设置为了leftright那么会导致rightmid此后一直判断一直rightmid一直死循环下去求中点原本是有两种写法的但此处需要考虑特殊情况当数据剩余最后两个元素的时候a.选用上图中的第1种情况才是正确的求中点操作此时求出的mid为靠左边的数此时若命中条件1left右移不满足判断条件跳出循环程序正常结束若此时命中条件2right左移不满足判断条件跳出循环程序正常结束b.若选用上图中的第2种情况时此时求出的mid为靠右边的数该种情况会导致进入死循环此时如果判断命中了条件1此时left右移动到mid1此时程序结束但此时如果判断命中了条件2此时会发现right原地不动当下次进入循环的时候判断后依旧保持原样此时进入了死循环2.查找区间右端点处理细节循环条件同左端点里的解释leftright求中点分析和求左端点里是类似的这里必须用left(right-left1)/2否则会陷入死循环最后附上模板x的平⽅根easy69. x 的平方根 - 力扣LeetCode思考出if条件后走模板即可搜索插⼊位置easy35. 搜索插入位置 - 力扣LeetCode思路分析发现实际要做的工作可以合并成找出大于等于target的那个数或者位置。可以利用二段性⼭峰数组的峰顶easy852. 山脉数组的峰顶索引 - 力扣LeetCode解法二分查找算法思路分析峰顶位置的数据特点以及山峰两旁的数据的特点a. 峰顶数据特点arr[i] arr[i - 1] arr[i] arr[i 1] b. 峰顶左边的数据特点arr[i] arr[i - 1] arr[i] arr[i 1] 也就是呈现上升趋势c. 峰顶右边数据的特点呈现下降趋势。因此根据 arr[i] arr[i - 1] arr[i] arr[i 1] 也就是 mid 位置的信息我们可以分为下面的情况a. 如果 mid 位置呈现上升趋势说明我们接下来要在 [mid 1, right] 区间继续搜索b. 如果 mid 位置呈现下降趋势说明我们接下来要在 [left, mid - 1] 区间搜索c. 如果 mid 位置就是山峰直接返回结果。寻找峰值medium162. 寻找峰值 - 力扣LeetCode解法二分查找算法算法思路寻找二段性任取一个点 i 与下一个点 i 1 会有如下两种情况arr[i] arr[i 1] 此时左侧区域一定会存在山峰因为最左侧是负无穷那么我们可以去左侧去寻找结果arr[i] arr[i 1] 此时右侧区域一定会存在山峰因为最右侧是负无穷那么我们可以去右侧去寻找结果。当我们找到二段性的时候就可以尝试用二分查找算法来解决问题。可以分析出下面的情况然后根据这两个if条件就能写出代码了我们比较nums[mid]和nums[mid1]只有两种情况情况一nums[mid] nums[mid1]mid 处在下降趋势nums[mid] \ \ nums[mid1] \mid 位置本身就是一个下降点。这意味着峰值要么就是 mid要么在 mid 左边。mid 右边不可能有峰值因为 mid 到 mid1 已经在下降了但我们不确定 mid 自己是不是峰值——它可能左边还有更高的。所以right mid保留 mid因为 mid 本身可能就是答案情况二nums[mid] nums[mid1]mid 处在上升趋势nums[mid1] / / nums[mid] /mid 位置在上升说明mid 本身一定不是峰值它右边的邻居比它大。峰值一定在 mid 右边。所以left mid 1跳过 mid因为 mid一定不是答案搜索旋转排序数组中的最⼩值medium153. 寻找旋转排序数组中的最小值 - 力扣LeetCode解法二分查找算法思路题目中的数组规则如下图所示其中 C 点就是我们要求的点图片中的n-1表示的是最后一个位置的值我们都是用最后一个位置的值来做比较的二分的本质找到一个判断标准使得查找区间能够一分为二。通过图像我们可以发现[AB] 区间内的点都是严格大于 D 点的值的C 点的值是严格小于 D 点的值的。但是当 [CD] 区间只有一个元素的时候C 点的值是可能等于 D 点的值的。因此初始化左右两个指针 left right 然后根据 mid 的落点我们可以这样划分下一次查询的区间当 mid 在 [AB] 区间的时候也就是 mid 位置的值严格大于 D 点的值下一次查询区间在 [mid 1right] 上当 mid 在 [CD] 区间的时候也就是 mid 位置的值严格小于等于 D 点的值下次查询区间在 [leftmid] 上。当区间长度变成 1 的时候就是我们要找的结果。0〜n-1中缺失的数字easyLCR 173. 点名 - 力扣LeetCode解法二分查找算法算法思路关于这道题中时间复杂度为 O(N) 的解法有很多种这里直接上手最优解其他解法末尾会讲到的。讲一个最优的二分法来解决这个问题。在这个升序的数组中我们发现在第一个缺失位置的左边数组内的元素都是与数组的下标相等的在第一个缺失位置的右边数组内的元素与数组下标是不相等的。因此我们可以利用这个二段性来使用二分查找算法。LCR 173. 点名 —— 四种 O(n) 解法详解某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组records。假定仅有一位同学缺席请返回他的学号。示例输入:records [0, 1, 2, 3, 5]→ 输出: 4输入:records [0, 1, 2, 3, 4, 5, 6, 8]→ 输出: 7关键信息数组是升序的学号从 0 开始连续编号恰好缺一个人缺失的可能在中间也可能在末尾如[0,1,2,3]缺 4解法一哈希表思路把数组中所有出现过的学号存入哈希表然后从 0 开始逐个检查哪个学号不在哈希表中。int takeAttendance(vectorint records) { unordered_setint seen; for (int r : records) { seen.insert(r); // 把所有出现的学号存入哈希表 } ​ for (int i 0; i records.size(); i) { if (seen.find(i) seen.end()) { return i; // 第一个不在哈希表中的就是缺席的 } } return -1; }执行过程演示records [0, 1, 2, 3, 5]第1步: 建哈希表seen {0, 1, 2, 3, 5}第2步: 从 0 开始逐个检查i0: 在 seen 中 ✓i1: 在 seen 中 ✓i2: 在 seen 中 ✓i3: 在 seen 中 ✓i4: 不在 seen 中 → 返回 4 ✓复杂度时间 O(n)遍历建表 遍历查找空间 O(n)哈希表存储 n 个元素优缺点优点最直觉、最通用。即使数组无序也能用缺点空间复杂度 O(n)多了一次遍历效率最低能写出来说明你懂基础数据结构但面试官可能会追问能不能不用额外空间解法二直接遍历找结果思路因为数组升序且学号从 0 开始连续编号所以正常情况下records[i]应该等于i。第一个records[i] ! i的位置缺失的就是i。如果全部相等缺失的就是最后一个records.size()。int takeAttendance(vectorint records) { for (int i 0; i records.size(); i) { if (records[i] ! i) { return i; // 第一个学号和下标不匹配的位置 } } return records.size(); // 都匹配缺的是最后一个 }执行过程演示例1: records [0, 1, 2, 3, 5]下标01234学号01235匹配✓✓✓✓✗i4 时 records[4]5 ≠ 4 → 返回 4 ✓例2: records [0, 1, 2, 3]下标0123学号0123匹配✓✓✓✓全部匹配 → 返回 records.size()4 ✓为什么这个方法成立数组升序学号从 0 开始连续编号。如果没缺人records [0, 1, 2, ..., n-1]每个位置records[i] i。如果缺了某个人k那么从位置k开始后面的学号都比下标大 1records [0, 1, 2, 3, 5] → 缺了4从位置4开始 records[i] i1records [0, 1, 3, 4, 5] → 缺了2从位置2开始 records[i] i1所以第一个records[i] ! i的下标i就是缺失值。复杂度时间 O(n)最坏遍历整个数组空间 O(1)优缺点优点代码简洁空间 O(1)利用了升序性质缺点时间 O(n)没有利用升序性质做到 O(log n)面试官会认可但会追问数组是有序的能不能更快 → 引出二分查找解法三位运算异或 XOR思路利用异或运算的两个性质a ^ a 0相同数异或为 0、a ^ 0 a任何数异或 0 为自身。把数组中所有元素和0 到 n 的所有完整学号异或在一起成对出现的会抵消为 0最后剩下的就是缺失的那个数。int takeAttendance(vectorint records) { int xorResult 0; ​ // 把数组中所有学号异或进去 for (int r : records) { xorResult ^ r; } ​ // 把完整学号 0 到 n 异或进去n records.size()因为缺了一个 for (int i 0; i records.size(); i) { xorResult ^ i; } ​ return xorResult; }执行过程演示records [0, 1, 2, 3, 5], n 5数组有5个元素完整应有0~5共6个学号第1步: 异或数组中所有元素0 ^ 1 ^ 2 ^ 3 ^ 5 0 ^ 1 1 → 1 ^ 2 3 → 3 ^ 3 0 → 0 ^ 5 5xorResult 5第2步: 异或完整学号 0 ~ 55 ^ 0 5 → 5 ^ 1 4 → 4 ^ 2 6 → 6 ^ 3 5 → 5 ^ 4 1 → 1 ^ 5 4xorResult 4 ✓为什么是 4因为(0^0) ^ (1^1) ^ (2^2) ^ (3^3) ^ 4 ^ (5^5) 0 ^ 0 ^ 0 ^ 0 ^ 4 ^ 0 4直觉理解想象你有两组数字完整学号: [0, 1, 2, 3, 4, 5] ← 应该有的实际到场: [0, 1, 2, 3, 5] ← 实际有的缺了 4把两组数字混在一起异或成对的0和0、1和1、...全部抵消为 0只剩下多出来的那个 4。为什么循环到 records.size()数组有n个元素缺了 1 个所以完整学号应该是0到n共n1个。比如records [0,1,2,3,5]有 5 个元素完整应该是0~5共 6 个缺的是 4。所以异或完整学号要循环到records.size()即 5包含 5。复杂度时间 O(n)两次遍历空间 O(1)优缺点优点空间 O(1)不需要数组有序即使数组打乱了也能用思路巧妙缺点两次遍历常数项比解法二大能展示你对位运算的理解。面试官可能会问异或的顺序重要吗 → 不重要异或满足交换律和结合律。解法四数学高斯求和公式思路如果一个人都不缺学号 0 到 n 的总和是0 1 2 ... n n(n1)/2高斯求和公式。现在缺了一个人实际总和 理论总和 - 缺失的学号。所以缺失的学号 理论总和 - 实际总和int takeAttendance(vectorint records) { int n records.size(); // 数组有 n 个元素完整应有 n1 个学号(0~n) ​ // 理论总和: 0 1 2 ... n n*(n1)/2 int expectedSum n * (n 1) / 2; ​ // 实际总和 int actualSum 0; for (int r : records) { actualSum r; } ​ // 差值就是缺失的学号 return expectedSum - actualSum; }执行过程演示records [0, 1, 2, 3, 5], n 5第1步: 理论总和 expectedSum 5 * 6 / 2 15即 012345 15第2步: 实际总和 actualSum 0 1 2 3 5 11第3步: 缺失学号 15 - 11 4 ✓为什么 n records.size()数组有n个元素意味着到场了n个人。因为缺了 1 个所以总共有n1个学号0 到 n。因此理论总和是01...n n*(n1)/2。复杂度时间 O(n)遍历一次求和空间 O(1)优缺点优点一次遍历空间 O(1)不需要数组有序打乱了也能用数学思路优雅缺点n*(n1)/2可能溢出当 n 很大时需要用long long溢出问题当n 10000时n*(n1)/2 50005000int范围足够约 21 亿。但如果 n 更大需要用long longlong long expectedSum (long long)n * (n 1) / 2; long long actualSum 0; for (int r : records) actualSum r; return expectedSum - actualSum;面试官最喜欢的解法之一。简洁、高效。可能会追问如果缺失的不是一个而是两个呢 → 高斯公式不再直接适用需要其他方法。四种解法对比总表解法时间空间需要有序核心思想哈希表O(n)O(n)不需要查表判断哪个学号没出现直接遍历O(n)O(1)需要学号和下标应相等不等处就是缺失位运算O(n)O(1)不需要完整学号和实际学号异或成对抵消剩缺失高斯求和O(n)O(1)不需要理论总和 - 实际总和 缺失值面试官: 怎么找缺失的学号你: 我想到几种方法: 1. 最直觉的哈希表但空间 O(n)2. 利用有序直接遍历看 records[i] ! iO(1) 空间3. 不依赖有序的高斯求和理论和减实际和一次遍历 O(1) 空间4. 同样不依赖有序的位运算异或成对抵消。其中 2 利用有序做到了最简洁如果要更快数组有序可以用二分查找做到 O(log n)面试官: 那就写最优的二分查找O(log n)策略:先给出多种解法展示思维广度再写最优解展示深度。面试官不仅看你的代码更看你分析问题的角度。