青岛做网站排名北京app开发

青岛做网站排名,北京app开发,抖音代运营是做什么,申报网站建设理由 模板这篇文章通过一道经典题目#xff1a;LeetCode 153「Find Minimum in Rotated Sorted Array」#xff0c;从零拆解二分搜索的两大模板、区间含义#xff0c;以及为什么会出现各种神秘的条件#xff0c;例如 while (left right)、right mid 这种看起来不直…这篇文章通过一道经典题目LeetCode 153「Find Minimum in Rotated Sorted Array」从零拆解二分搜索的两大模板、区间含义以及为什么会出现各种神秘的条件例如 while (left right)、right mid 这种看起来不直观的写法。leetcode1​题目回顾题意简述有一个严格递增的有序数组被旋转了若干次1 到 n 次。数组中的元素互不相同。要求在 O(log⁡n)O(\log n)O(logn) 时间内找出数组中的最小值。algo1​典型例子[0,1,2,4,5,6,7] → 旋转 4 次 → [4,5,6,7,0,1,2]最小值是 0[11,13,15,17] → 旋转 4 次 → 还是 [11,13,15,17]最小值是 11其实没变leetcode​直观思路找「跳变点」从直觉上看最小值就是从大突然变小的那个位置也就是拐点 / 跳变点在原始升序数组中不存在这种下降旋转之后只会出现一次从大到小的跳变这个位置就是最小值。因此一个自然的想法是默认最小值在 nums[0]。用二分找一个 mid判断它是不是跳变点如果 nums[mid - 1] nums[mid] 且 nums[mid 1] nums[mid]那 mid 就是最小值。否则通过比较决定向左还是向右缩小区间。这个方向在思维上没有问题但在具体实现上会遇到几个麻烦要访问 mid - 1 / mid 1很容易在 mid 0 或 mid n - 1 时越界。条件会比较复杂不够稳定和通用。面试里更推荐的是一套更简洁、更稳定的模板化写法。二分的两套经典模板理解这道题之前先把二分的两种常见模板说清楚。stackoverflow2​模板一存在性查询 while (left right)典型用于“数组里有没有 target返回下标没有就返回 -1”。geeksforgeeks1​伪代码intsearch(vectorintnums,inttarget){intleft0,rightnums.size()-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){returnmid;// 找到直接返回}elseif(nums[mid]target){leftmid1;// 排除掉 mid 以及左边}else{rightmid-1;// 排除掉 mid 以及右边}}return-1;// 跑完 while 表示没找到}特征区间是闭区间 [left, right]表示 target 可能存在于其中。nums[mid] target 时在循环内部直接 return。每次更新都是 mid ± 1把 mid 本身从区间中移除。循环结束时一定是 left right因为最后一次 left right 那轮已经在 while 里消耗掉了。要么在那一轮找到并 return要么那一轮之后变成 left right 1 或 right left - 1也就是 left right。stackoverflow1​这就是为什么这种模板的结束状态是 left right 而不是 left right。模板二收缩到一个点 while (left right)典型用于找边界、找最小值、找第一个/最后一个满足条件的位置本题就属于这一类。labuladong1​伪代码通用形式intleft0,rightn-1;while(leftright){intmidleft(right-left)/2;if(某个条件成立){// 最小值在 mid 右侧leftmid1;}else{// 最小值在左侧包括 mid 本身rightmid;}}// 循环结束时left rightreturnleft;// 或 nums[left]特征区间仍然是闭区间 [left, right]表示答案一定在这个区间中。循环目标不是找到就返回而是把区间不断缩小直到只剩一个位置。循环条件是 left right因此退出时必然是 left right。整个过程中始终维护 left right不会出现 left right。w3tutorials1​回到本题为什么是 right mid 而不是 right mid - 1这道题的经典写法你已经写出来了是intfindMin(int*nums,intnumsSize){intleft0,rightnumsSize-1;// 如果本来就是有序且没旋转直接返回最左if(nums[left]nums[right])returnnums[left];while(leftright){intmidleft(right-left)/2;if(nums[mid]nums[right]){// 最小值一定在 mid 右边leftmid1;}else{// 最小值在左边包含 mid 自己rightmid;}}returnnums[left];}关键就在 else 分支这句为什么是 right mid而不是 left mid 或 right mid - 1geeksforgeeks1​思路拆解nums[mid] nums[right]右端 right 所在的这一段是被旋转后的尾部比前面那段小。如果 mid 这一点比 right 还大说明 mid 一定在左边那段较大的递增区间里最小值一定在 mid 右边。所以安全地排除掉 mid 以及其左边写成left mid 1。read.learnyard1​nums[mid] nums[right]也就是 else说明从 mid 到 right 这一段是整体有序且数值偏大的一截最小值不可能在 mid 右边。此时最小值要么在 mid要么在 mid 左边。因此 mid 是一个合法的候选位置不能被排除。为了继续二分缩小区间同时保留 mid只能写right mid。algo1​如果你写成right mid - 1会把 mid 排除掉而这一支的含义正是最小值有可能在 mid排除掉会漏解。left mid在 left right 时mid 可能等于 left这样会导致区间不变形成死循环。从「区间语义」看这件事这一整套写法的核心不在于具体比较而在于始终维护这样一个不变式在任意时刻最小值一定在 [left, right] 这个区间内。于是在排除右侧时要用 left mid 1因为最小值不可能在 mid 以及左边。在排除左侧时要用 right mid 而不是 right mid - 1因为最小值有可能就是 mid。而 while (left right) 配合这样的更新方式保证区间大小严格缩小最终收敛到 left right 这个唯一的候选位置。vultr1​再看一眼完整代码这是你通过题目的 C 代码已经是教科书式写法intfindMin(int*nums,intnumsSize){intleft,right,mid;left0;rightnumsSize-1;if(nums[left]nums[right])returnnums[left];while(leftright){midleft(right-left)/2;if(nums[mid]nums[right])leftmid1;elserightmid;}returnnums[left];}特点先特判完全没旋转的情况首元素小于尾元素直接返回首元素。使用 while (left right)通过比较 nums[mid] 和 nums[right] 进行分割。保证最小值始终在 [left, right]且区间不断缩小到一个点。ducmanhphan.github1​如何从这道题迁移到其它二分题可以给自己几个思考练习1. 什么时候应该用 while (left right) 模板答需要在中途直接返回结果且找不到时要通过 left right 表示区间为空的题。2. 什么时候应该用 while (left right) 模板答要找边界/极值最终答案总是某个边界点的题比如旋转数组的最小值找第一个大于等于 target 的位置找山峰 / 谷底等。towardsdatascience1​3. 写二分前先问自己两件事我的区间 [left, right] 的语义是什么答案一定在里面还是可能不在更新的时候是要排除 mid还是要把 mid 当成候选保留这道题就是典型的答案一定在区间内 需要把 mid 作为候选保留的场景所以用的是 while (left right) right mid 这一套模板。理解了这点后面很多神秘条件自然就顺了。