【Java实习面试算法冲刺】二分

第7类题型二分为什么二分题你明明背过模板一到面试还是容易写出死循环很多同学第一次刷二分会觉得它比链表、回溯简单因为代码看起来就十几行。但真正到面试现场二分反而特别容易暴露基本功问题。原因不是你不会比较大小而是你没有真正固定自己的区间定义。二分题最常见的翻车方式通常就这几种你背过闭区间和左闭右开两个版本结果写题时混用了。你知道要算mid但边界更新时没有把mid排除出去直接把循环写成死循环。你能做“找到目标值”一到“找左边界、右边界、插入位置”就开始发虚。如果你现在处在“模板大概会背但每次都怕边界写错”的阶段这一类题一定要单独练透。读完这篇你至少要把 3 件事彻底练熟先判断题目有没有单调性、先固定一套区间模板、能在面试里解释为什么当前这次更新不会漏答案。文章目录第7类题型二分为什么二分题你明明背过模板一到面试还是容易写出死循环1. 核心知识点动画辅助理解二分真正缩掉的是什么2. 这类题在面试里考什么3. 高频题清单4. 这类题最容易犯的 3 个错误5. 代表题精讲 1题目思路Java 代码复杂度边界提醒如果这是面试现场你可以这样说6. 代表题精讲 2题目思路Java 代码复杂度边界提醒如果这是面试现场你可以这样说7. 其余题模板与关键片段[35. 搜索插入位置](https://leetcode.cn/problems/search-insert-position/)8. 二分类题先判断什么9. 错题本记录方式10. 面试前 3 分钟速记11. 最后总结二分真正难的不是模板而是边界纪律1. 核心知识点二分最核心的不是“找中点”而是“在有序或满足单调性的范围里每次排除掉一半不可能的答案”。这篇统一使用闭区间[left, right]。只要你选了这套定义后面的循环条件和边界更新就必须跟着一起固定intleft0;intrightnums.length-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){returnmid;}elseif(nums[mid]target){leftmid1;}else{rightmid-1;}}这里有 3 个关键点left right因为闭区间里left right时仍然可能有答案。mid left (right - left) / 2避免溢出也更稳。更新边界时必须写成mid 1或mid - 1因为mid已经比较过不能继续留在待搜索区间里。动画辅助理解二分真正缩掉的是什么你可以先打开这页分步动画二分区间定义与边界收缩分步动画这个动画最值得盯住的是 4 步先说清楚区间到底是闭区间[left, right]还是左闭右开[left, right)。再稳定算出mid保证比较位置明确。根据nums[mid]和target的关系丢掉确定不可能的一半。继续收缩直到区间完全收敛。拿数组nums [1, 3, 5, 7, 9]、target 8举例轮次leftrightmidnums[mid]结论第 1 轮04255 8左半边和mid都不可能left 3第 2 轮34377 8继续右移left 4第 3 轮44499 8排除右侧right 3结束43--left right说明没找到插入位置就是left 4这张表最重要的不是结果而是你要看清楚每一轮都必须让区间真实变小。只要某一轮比较完以后还把mid留在区间里二分就容易卡住。2. 这类题在面试里考什么二分题真正考的不是模板记忆而是你能不能在极少的代码里把边界处理得非常干净。面试官通常会看你能不能先判断题目是否具备单调性或有序性。你是否固定了一套区间定义而不是边写边变。你会不会把mid的更新写错导致漏答案或死循环。你能不能从“找目标值”平滑扩展到“找边界”和“找插入位置”。真正的区分度在于你不只是把代码写出来还能解释为什么当前边界更新一定不会漏掉正确答案。3. 高频题清单题目来源难度高频属性704. 二分查找LeetCode 热题 100Easy面试高频35. 搜索插入位置面试经典 150Easy高频34. 在排序数组中查找元素的第一个和最后一个位置LeetCode 热题 100Medium高频 Medium4. 这类题最容易犯的 3 个错误区间定义没固定闭区间和左闭右开混着写。边界更新没有排除mid导致区间不收缩。只会标准二分不会把模板改造成左边界、右边界或插入位置。5. 代表题精讲 1题目704. 二分查找思路这是最标准的模板题核心不是“写出来”而是“每一步都能解释清楚为什么这么写”。流程非常稳定用left和right表示当前候选区间。取中点mid进行比较。命中就直接返回。如果nums[mid] target说明目标只可能在右边left mid 1。如果nums[mid] target说明目标只可能在左边right mid - 1。Java 代码classSolution{publicintsearch(int[]nums,inttarget){intleft0;intrightnums.length-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){returnmid;}elseif(nums[mid]target){leftmid1;}else{rightmid-1;}}return-1;}}复杂度时间复杂度O(log n)空间复杂度O(1)边界提醒这题最容易出错的地方有两个循环条件必须和区间定义配套。既然用的是闭区间[left, right]就必须写left right。更新边界时不能写成left mid或right mid。因为mid已经比较过了继续保留会导致区间缩不动。你可以自己代一个最容易挂的样例nums [5]target 2。如果你写成right mid那第一轮mid就还是0区间不会收缩循环就容易卡死。如果这是面试现场你可以这样说这题是标准二分模板题前提是数组有序。我这里统一使用闭区间[left, right]所以循环条件写left right。每一轮比较nums[mid]和target后都能明确排除一半区间而且边界更新必须写成mid 1或mid - 1保证当前比较位置不会被重复保留在区间里。6. 代表题精讲 2题目34. 在排序数组中查找元素的第一个和最后一个位置思路这题最重要的认知是它不是“一次二分找两个答案”而是“两次二分分别找左右边界”。为什么要拆成两次找左边界时即使命中了target也不能立刻停因为前面可能还有更靠左的目标值。找右边界时同理也要继续往右压缩看看后面还有没有目标值。所以逻辑会变成找左边界只要nums[mid] target就往左收缩。找右边界只要nums[mid] target就往右收缩。Java 代码classSolution{publicint[]searchRange(int[]nums,inttarget){intleftfindLeft(nums,target);intrightfindRight(nums,target);returnnewint[]{left,right};}privateintfindLeft(int[]nums,inttarget){intleft0;intrightnums.length-1;intanswer-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){if(nums[mid]target){answermid;}rightmid-1;}else{leftmid1;}}returnanswer;}privateintfindRight(int[]nums,inttarget){intleft0;intrightnums.length-1;intanswer-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){if(nums[mid]target){answermid;}leftmid1;}else{rightmid-1;}}returnanswer;}}复杂度时间复杂度O(log n)空间复杂度O(1)边界提醒这题最容易错的不是两次二分本身而是“命中 target 之后到底停不停”。比如nums [5, 7, 7, 8, 8, 10]target 8找左边界时如果你在第一次命中8时就直接返回很可能拿到的是下标4不是最左边的3。找右边界时如果命中后不继续向右试探就可能只能拿到中间某个8而不是最后一个位置。因此这题要记住一句话命中目标值不代表结束边界题要看“命中后是否还要继续收缩”。如果这是面试现场你可以这样说这题我会拆成两次二分。第一次专门找最左出现位置所以在nums[mid] target时继续往左压缩第二次专门找最右出现位置所以在nums[mid] target时继续往右压缩。关键不在于“有没有找到 target”而在于“命中之后是否还要继续寻找更靠左或更靠右的答案”。7. 其余题模板与关键片段35. 搜索插入位置这题和704的模板几乎一样只是如果最后没找到返回值不是-1而是leftclassSolution{publicintsearchInsert(int[]nums,inttarget){intleft0;intrightnums.length-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){returnmid;}elseif(nums[mid]target){leftmid1;}else{rightmid-1;}}returnleft;}}为什么最后返回left如果目标值存在前面已经返回了。如果不存在循环结束时left正好停在“第一个大于等于 target 的位置”。如果数组里所有数都比target小那left最后会走到nums.length这正好也是尾部插入的位置。8. 二分类题先判断什么真正动手写之前你可以先问自己 4 个问题这题是不是建立在有序数组或单调性之上。我这次统一用闭区间还是左闭右开。我当前是在找“某个值”还是在找“某个边界”。命中目标值之后我是可以返回还是还要继续收缩区间。这 4 个问题一旦提前问清楚二分题大部分边界错误都能少掉一半。9. 错题本记录方式二分题建议重点记录这题的单调性到底是什么。我使用的是哪套区间定义。哪一轮边界更新没有把区间真正缩小。这题是在找目标值、插入位置还是左右边界。10. 面试前 3 分钟速记二分先看“有序 / 单调”。先固定一套区间定义不要混写。mid left (right - left) / 2。更新边界时必须排除已经比较过的mid。找边界题时关键不是“命中没命中”而是“命中后还要不要继续缩”。11. 最后总结二分真正难的不是模板而是边界纪律如果你只能记住一句话那就是二分题最怕的不是不会写而是边界定义不统一导致你自己也不知道当前区间里还剩谁。面试时你只要按这个顺序去讲思路就会非常稳先说明这题为什么能二分是有序还是有单调性。再说明你选的是哪套区间定义。接着解释当前比较后为什么能排除左边或右边。如果是边界题再补一句“命中后为什么还不能立刻返回”。这样你就不只是会背一个模板而是真的掌握了二分这类题的公共骨架。上上期速递【Java实习面试算法冲刺】栈、队列与单调栈上期速递【Java实习面试算法冲刺】二叉树感谢阅读记得点赞、关注、收藏欢迎各位评论区交流