刷过Java面试的朋友应该都有体会十个面试官里至少有八个会问算法而二分查找Binary Search基本上属于必考范围内的“钉子户”。网上关于二分查找的教程一抓一大把但很多人看完后只是记住了代码没搞懂背后的边界条件推导结果题目一换、边界一改就翻车。这篇博文就围绕“Java二分算法题目练习”这个主题从最基础的模板推导到变体题目拆解再到面试答题思路和调试技巧一次性把这些东西捋清楚。内容适合准备Java面试的候选人、正在刷LeetCode的在校生以及工作中需要手写算法但总在边界条件上栽跟头的开发同学。1. 内容整体设计与思路拆解1.1 为什么二分算法是Java面试的“必考题”二分查找本身逻辑并不复杂十几行代码就能写完但它背后的考察点非常密集循环不变量的设计、整数溢出的处理、边界条件的推演、时间复杂度分析以及在不同场景下的变体应用。这些恰恰是面试官判断候选人基本功是否扎实的高效试金石。我在面试候选人的时候对二分查找这道题有个执念如果对方能一次性写出正确代码大概率基础是扎实的如果花了很长时间调边界或者写出了死循环那后面关于复杂度的追问基本也就不太乐观了。原因在于二分查找太“小”了小到没有太多复杂业务逻辑可以包装整道题的成败几乎完全取决于一个关键点——你对区间定义的理解是否清晰。这种“越小越见真章”的特性决定了它在面试题里难以回避的地位。1.2 从暴力遍历到二分查找的思维转变很多初学者面对“在有序数组中查找目标值”这种题目第一反应是线性遍历从头扫到尾比较每个元素。这个思路没错复杂度O(n)在数据量小的时候完全够用。但你一旦遇到亿级数据量的场景线性扫描的时间开销就会让人无法接受这时候二分查找的O(log n)优势就体现出来了。对比一组直观数字就明白了数据量是10亿时线性查找最坏情况需要比较10亿次二分查找最多只需要比较30次因为2的30次方约等于10亿这个差距是几个数量级的。二分查找的思路说起来也很朴素——每一次比较都利用“有序”这个信息直接将搜索范围缩小一半。用个生活化的类比查英语字典的时候你不会从第一页开始翻而是会根据目标单词的首字母直接翻到词典中部区域再根据第二个字母决定往前翻还是往后翻。这个“每次都砍掉一半”的做法就是二分查找的核心思想。1.3 二分查找的适用前提与边界认知这里必须强调一个容易被忽略的前提二分查找能发挥作用前提是数据必须是有序的。如果你的数据本身无序又要求只能使用一次查找操作那二分查找就无从谈起要么先排序再查找要么用哈希表换空间换时间。这看起来是废话但面试中经常出现“给你一个数组请你快速找到某个值”这种陷阱题数组如果没有排序很多候选人会条件反射式地写二分最后越界或者结果错误。更隐蔽的坑是“部分有序”的特殊形态。比如旋转排序数组原有序数组从某个位置切一刀左右两段交换位置它整体不是严格递增的但依然可以通过二分思路在O(log n)时间内完成查找只不过需要增加额外判断来确定哪半边是有序的。这种变体题目在LeetCode上非常经典后面章节我会用整节来拆解。2. 核心细节解析与实操要点2.1 二分查找的两套基础模板很多人写二分查找翻车深层原因是自己脑子里同时装了好几套模板今天用左闭右闭明天用左闭右开一会儿while (left right)一会儿while (left right)边界一换就彻底混乱。这里建议你只选择一套模板作为主模板反复练到肌肉记忆。第一套是左闭右闭[left, right]写法也是我最推荐初学者掌握的模板public int binarySearch(int[] nums, int target) { int left 0; int right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return -1; }这套模板的核心逻辑是left和right指向的元素始终处于“待搜索区间”内区间是闭合的所以当left right时区间里仍然有一个元素没被检查循环条件必须用。当nums[mid]小于目标值时说明mid及其左侧所有元素都小于目标left收缩到mid 1反之right收缩到mid - 1。第二套是左闭右开[left, right)写法public int binarySearch(int[] nums, int target) { int left 0; int right nums.length; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; } else { right mid; } } return -1; }这套模板里right指向的元素不参与搜索所以right初始化为nums.length而不是nums.length - 1。nums[mid]大于目标时right mid因为mid已经不可能是目标而且右边界本身不参与搜索。这两种模板没有绝对优劣核心是选定后就不要摇摆。2.2 循环不变量写出正确二分的关键思维“循环不变量”这个词听起来很学术却说透了二分查找的本质——每一轮循环开始前目标值只可能存在于当前区间left, right]或[left, right]内。只要你在循环体内对left或right的更新遵守这个区间定义整个算法就一定是正确的。实际操作中最常见的错误就是在左闭右闭模板中把right mid - 1写成了right mid。这个错误会导致什么当目标值位于区间左边界时left和right会无限趋近同一个位置循环永远不会退出——也就是死循环。反过来在左闭右开模板中把right mid错写成right mid - 1则可能跳过目标值直接返回错误的-1。我给读者的建议是先花半小时把两套模板都默写一遍理解它们为什么这样写然后选定一套作为主用模板。面试的时候不要中途更换否则极容易翻车。2.3 整数溢出的隐蔽陷阱mid计算方式很多人会把求中位数的代码写成int mid (left right) / 2这在绝大多数时候没问题但存在一个隐蔽的溢出风险当left和right都非常大时它们的和可能超过int类型的最大值21亿左右。比如left 15亿right 15亿left right 30亿这个值已经超出了int的表示范围结果会变成负数数组下标随之出错。正确的写法是int mid left (right - left) / 2或者使用Java 21开始支持的Math.floorDiv(left right, 2)注意很多老版本还不行先求差值再除以2从数学上避免了left right的溢出问题。虽然在实际笔试中数组长度一般不会大到触发这个bug但面试官很爱在这里“钓鱼”写出来的代码得经得起追问。2.4 二分查找的时间复杂度分析分析二分查找的时间复杂度核心是“每次迭代后搜索区间缩小为原来的一半”。一个长度为n的有序数组经历k次迭代后搜索区间长度变为n / 2^k。当区间长度为1时仍需再进行一次比较才能确认结果因此总迭代次数k满足n / 2^k ≤ 1即k ≥ log2(n)。所以最坏时间复杂度是O(log n)空间复杂度为O(1)因为算法只用了常数级别的辅助变量。面试时如果被问到“为什么是O(log n)”不要只说“因为每次减半”——这种回答太浅。你可以补充说明对数复杂度的含义是随着数据量翻倍计算耗时只增加一个常量级的迭代次数然后给出那个经典的“10亿数据只需30次比较”的例子面试观感会好很多。3. 实操过程与核心环节实现3.1 基于二分模板的经典真题拆解标准查找先做一道最基础的题热热身在一个无重复元素的升序数组中找到目标值的下标不存在则返回-1。这是上面模板一的标准应用场景。写代码时注意几个细节数组长度为0时直接返回-1while循环里的等号不要丢mid计算用差值法。public int binarySearch(int[] nums, int target) { if (nums null || nums.length 0) { return -1; } int left 0; int right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return -1; }这道题虽然简单但作为练习模板的“标定题”非常合适。建议初学者用这道题做基准分别用左闭右闭和左闭右开两套模板实现跑通之后再进入变体题。3.2 核心变体一查找左边界第一个等于target的位置面试中二分查找的题目极少有“直接找目标值”那么客气。更常见的变体是数组中有重复元素要求返回目标值第一次出现的位置如果没有则返回插入位置。这就涉及到二分查找的“左边界”变体。以“找到target第一次出现的位置”为例public int findFirstPosition(int[] nums, int target) { int left 0; int right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { right mid - 1; } else if (nums[mid] target) { left mid 1; } else { right mid - 1; } } if (left nums.length nums[left] target) { return left; } return -1; }这段代码的关键改动在于当nums[mid] target时不立即返回而是将右边界左移继续在左半区寻找更靠左的目标值。循环结束后left指向的位置就是第一个等于target的位置如果存在。判断条件不能省因为有可能target根本不存在此时left可能等于nums.length越界或者nums[left] ! target。右边界同理只需要在nums[mid] target时执行left mid 1循环结束后right指向最后一个等于target的位置。这个变体在“统计有序数组里某个数出现的次数”这类问题中非常实用分别求出左右边界两个下标一减就是出现次数复杂度依然是O(log n)比线性扫描优雅得多。3.3 核心变体二有序数组中的搜索插入位置这道题是LeetCode第35题Search Insert Position考察点是对“当目标值不存在时二分查找最终停在哪里”的理解。题目要求给定一个排序数组和一个目标值在数组中找到目标值如果找不到则返回它将会被按顺序插入的位置。这里有个偷懒但有效的记忆方式插入位置其实就是第一个大于等于target的元素所在的下标。套用左边界模板等号处理稍做调整public int searchInsert(int[] nums, int target) { int left 0; int right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return left; }看到差别了吗传统二分里当nums[mid] target时是“相等即返回”而这里将等号并入了else分支目的是让right在相等时也向左收缩最终left停止的位置刚好是“第一个不小于target”的位置。如果target大于数组中所有元素while循环结束后left会变成nums.length这恰好也是合法的插入位置。这个细节就是区分“死记模板”和“理解原理”的分水岭。3.4 核心变体三旋转排序数组中的二分查找旋转排序数组可以理解为原升序数组从某个下标处拆开左右两段互换拼接。比如[1, 2, 3, 4, 5, 6, 7]在4处旋转后变成[4, 5, 6, 7, 1, 2, 3]。这种数组整体不是单调递增的但二分查找依然可以派上用场核心思路是“每次迭代先判断哪一半是有序的然后在有序的那一半中决定下一步搜索的方向”。public int searchRotated(int[] nums, int target) { int left 0; int right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } // 左半区有序 if (nums[left] nums[mid]) { if (target nums[left] target nums[mid]) { right mid - 1; } else { left mid 1; } } // 右半区有序 else { if (target nums[mid] target nums[right]) { left mid 1; } else { right mid - 1; } } } return -1; }这道题的易错点在于边界符号的取舍。判断target nums[left] target nums[mid]时用了左闭右开的思路mid已经被排除出搜索区间因为nums[mid]不等于target但如果target恰好等于nums[mid]理论上不可能因为上面的if已经判断过了这种写法也能规避重复判断。在实际面试中这一题如果能在15分钟内独立推导并写出正确代码说明你对二分查找的理解已经超过多数候选人了。3.5 工具链准备在本地打造二分算法的练习环境虽然LeetCode这类在线评测平台自带编译运行环境但我还是建议在本地搭建一个最小化的Java练习环境原因有两个一是培养使用IDE调试代码的能力二是方便自己写测试用例做基准测试。最省事的组合是JDK 17自带强类型校验和现代语法 IntelliJ IDEA社区版免费。遇到“本地Java环境跑不起来”的同学大多数问题出在环境变量配置上。Windows系统配置JAVA_HOME时路径一定要指向JDK的安装根目录比如C:\Program Files\Java\jdk-17不是bin目录配置PATH时追加的是%JAVA_HOME%\bin而不是写死路径这样以后升级JDK版本时不用反复改PATH。配置完成后命令行执行java -version能正确输出版本号说明环境就位了。如果你只求快速验证算法逻辑不想折腾IDE也可以用一个Java单文件运行技巧JDK 11起支持直接运行单个.java文件java Test.java即可执行不需要先javac编译。这个操作对于刷题场景非常顺手打开记事本都能跑算法。4. 常见问题与排查技巧实录4.1 死循环问题while条件与指针更新的错位写二分查找时最常见的报错就是Time Limit Exceeded超时翻译过来就是“死循环了”。排查思路很简单观察每轮循环后left或right是否一定会向对方靠拢。如果存在某条路径导致left和right都保持不变程序就会原地打转。举个例子左闭右闭模板里如果nums[mid] target时你写的是left mid而不是left mid 1当left和right相邻时就会出问题mid等于leftnums[mid]小于targetleft更新为mid还是原来的位置区间没有任何收缩死循环。解决这类问题的通用手段是在leetcode的测试用例里构造一个长度为2的极端数组手动走查一遍循环体很快就能定位到是哪个分支没有收缩。4.2 越界异常right初始值引发的低级错误使用左闭右开模板时right初始化为nums.length此时nums[right]是越界的所以循环体内绝对不能出现访问nums[right]的操作。很多从左闭右闭模板切换过来的同学会惯性写成nums[right] target的判断下标越界异常就出现了。反过来左闭右闭模板中right初始化为nums.length - 1如果target大于数组中全部元素left最终会变成nums.length此时再访问nums[left]同样越界。所以从循环里出来后凡是需要访问nums[left]或nums[right]的场景都要先判断下标是否在合法范围内。4.3 面试里的二分答题框架如何把代码讲清楚面试官让你写二分查找时输出正确代码只是及格线很多候选人忽略了“同步讲解”。我建议养成一个习惯先声明区间定义比如“我使用左闭右闭区间所以while里用小于等于”再写代码写完再解释为什么这样更新指针。这样做的好处是万一代码有小bug面试官也能看到你的思路是清晰的会在提示后让你修正而不是直接判定零分。如果面试官继续追问“这个算法能不能优化”常见延伸方向包括二分查找能否处理非升序数组降序数组需要改变比较符号能否在二维有序矩阵中使用LeetCode第74题将二维矩阵看成一维数组做二分即可找到目标值后能否更快地定位左右边界用两次二分而非从命中位置向两边线性扩。4.4 刷题路线建议从易到难的项目式练习清单二分算法虽然知识点不多但题目的变体和交叉场景非常丰富。我给读者整理了一条循序渐进的练习路径按这个顺序刷下来能建立起系统性理解阶段练习目标推荐题目基础入门掌握两种模板的写法与选择LeetCode 704二分查找、LeetCode 35搜索插入位置边界变体理解左右边界与重复元素的处理LeetCode 34排序数组中查找元素的第一个和最后一个位置旋转数组理解局部有序下的二分思路LeetCode 33搜索旋转排序数组、LeetCode 153寻找旋转排序数组中的最小值答案二分理解二分搜索答案而非搜索元素LeetCode 875爱吃香蕉的珂珂、LeetCode 410分割数组的最大值综合进阶二分与贪心、动态规划结合LeetCode 1011在D天内送达包裹的能力、LeetCode 1482制作m束花所需的最少天数“答案二分”这一类尤其值得关注。它的典型特征是题目不是让你在一个数组里找一个数而是让你找“一个满足条件的最小值/最大值”而这个值的搜索空间本身是单调的。比如LeetCode 875猴子吃香蕉找到在H小时内吃完所有香蕉的最小速度K。暴力解法是从1一直试到max(piles)但通过二分答案可以把复杂度从O(max(piles) * n)降为O(n * log(max(piles)))。这类题目对于开阔算法视野极有帮助面试中遇到类似“最小化最大值”的问题基本都能往二分答案上靠。4.5 关于调试的小经验如何肉眼定位边界错误写二分查找调试的时候不建议只会打系统输出那样速度太慢。我自己的做法是准备几个极端测试用例先跑一遍快速排除低级错漏空数组、只有一个元素的数组、两个元素的数组、目标值小于全部元素、目标值大于全部元素、数组中有重复目标值。这六类用例全部通过代码的健壮性基本就有保障了。如果某个用例还是挂了用IDE的断点调试功能在while循环开头打断点观察left、right、mid三个变量的变化轨迹。二分查找出错的模式很有限快速定位到某一轮循环中区间没有收缩或者收缩方向错误修正对应的分支即可。最后再分享一个我在练习过程中的体会二分算法非常适合用来锻炼“精确表达”的能力——左闭右闭还是左闭右开等于号放哪边指针收缩到mid还是mid±1每个细节都必须有明确依据糊弄不过去。所以刷二分题目不要贪多每天做1-2道每道题把模板变体和推导过程写清楚坚持两三周边界条件的敏锐度会有肉眼可见的提升。后续如果发现自己对“二分答案”的题目有感觉了再结合动态规划、图论等复杂场景交叉训练算法思维的基本功就越来越扎实了。