如果你今天刚打开一份Java学习路线图大概率会看到这样一行Day 1数据结构与算法——二分查找。我第一眼看到的时候觉得还挺友好毕竟看起来就是在一个有序数组里找一个数比链表、二叉树这些名词好懂多了。可真轮到自己动手写Java代码写出来的版本不是死循环就是漏掉边界元素要么直接返回了一个错误的下标。这篇东西想聊的就是二分查找从看得懂到写得对之间那几道坎为什么它被放在算法学习的第一天、标准实现里每一行到底在干什么、实际工程中又会以哪些变体出现。如果你正准备开始Java学习或者已经在刷在线题库时被边界条件折磨过这篇文章应该能帮你把这块地基打得稳一点至少以后看到任何在有序数据里定位的题目不会心里发怵。1. 为什么学习计划的第一天会从二分查找开始1.1 猜数字游戏最早接触到的二分思想如果你玩过猜数字游戏其实已经用过二分查找了。主持人心里想一个1到100之间的整数你每次猜一个数对方只说大了或小了最坏情况下猜几次能保证命中答案是7次。为什么是7因为每猜一次可选的数字范围就砍掉一半100变成5050变成2525变成13……一直到1。这个每次缩小一半候选范围的过程就是二分思想最原始的形态。这个例子看起来简单但它揭示了算法学习中一个很关键的信号解决一个问题之前先要确认数据环境。二分查找能成立靠的是有序性这个前提。数组必须是有序的否则大小比较没有任何指导意义——你比较完arr[mid]大还是小剩下的半个区间里可能仍然散落着目标值砍掉哪一半都可能是错的。很多初学者觉得二分查找难其实不是难在砍一半这个动作而是难在基于什么信息去砍。1.2 从公式到区间收缩模型读第一遍资料时很多人会去背二分查找的模板背完再默写总感觉差一口气。问题出在把二分查找当成一套公式来记而不是当成一个区间收缩的过程来理解。二分查找的真正抽象模型是用两个指针left和right圈出目标值可能存在的一段区间每一轮取区间中点mid和target做一次比较。比较得到三种结果相等直接命中目标值更大说明目标只可能落在右半段目标值更小说明目标只可能落在左半段。无论哪种结果本轮之后搜索区间都严格变小——这就是它时间复杂度是O(log n)的根本原因。在Java里这个模型落地的形式很直白维护两个int变量作为下标写一个while循环不断收缩区间。空间复杂度是O(1)因为你只额外用了几个变量。这也是数据结构与算法第一天适合选它的原因它不依赖任何复杂的数据结构只要数组有序就行但它把算法最核心的几件事全带出来了——循环不变量、边界处理、复杂度分析、以及从问题中抽象模型的能力。这些东西练扎实了后面学二叉树、红黑树、跳表时都会反复用到。2. 手写第一版二分查找把直觉翻译成Java代码2.1 区间定义闭区间和左闭右开必须选一套开始写代码之前第一件事不是写while而是先想清楚你维护的区间是什么。常见的定义有两套闭区间[left, right]left和right指向的位置都可能是目标值初始时left0rightarr.length - 1。左闭右开区间[left, right)left指向的位置可能是目标值right不参与搜索初始时left0rightarr.length。这两套都能写出正确的二分查找但它们对应的循环条件、指针更新方式完全不一样。闭区间用while (left right)因为当left等于right时当前这个位置还没有被检查左闭右开用while (left right)因为当left等于right时区间已经为空。我给初学者的建议是第一版先认准闭区间这一套不要混着用。等闭区间写法足够熟练了再去了解左闭右开的写法。混用是新手最常见的翻车原因——一会儿觉得right应该减一一会儿觉得不用减最后写出来一个自己也说不清楚对不对的东西。2.2 中点计算一道防溢出的小算术题标准写法里中点的计算不是(left right) / 2而是left (right - left) / 2。很多第一眼看不懂这两个式子长得几乎一样为什么非要绕一圈因为(left right)在极端情况下会超过int类型的最大值2147483647。数组长度一般在内存中也到不了那么大但工程代码里没人能保证你手里的下标是从0到几百万还是从几十亿的某个位置开始的。两个接近int上限的数相加结果会变成负数导致mid变成负数再取arr[mid]直接抛数组越界。left (right - left) / 2先算差值再除以2把计算控制在安全的范围内这个写法成本很低建议从一开始就养成习惯。2.3 标准实现与逐行拆解下面这个版本是我认为最适合作为第一版学习的Java实现闭区间逻辑直接。public class BinarySearchDemo { /** * 在升序数组中查找目标值 * * param arr 升序数组 * param target 要查找的目标值 * return 目标值下标不存在时返回 -1 */ public static int binarySearch(int[] arr, int target) { int left 0; int right arr.length - 1; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { return mid; } else if (arr[mid] target) { left mid 1; } else { right mid - 1; } } return -1; } public static void main(String[] args) { int[] arr {1, 3, 5, 7, 9, 11}; System.out.println(binarySearch(arr, 7)); // 3 System.out.println(binarySearch(arr, 6)); // -1 } }拆开看每一步的意图。left 0和right arr.length - 1规定搜索范围是整个数组中所有可能的位置。while (left right)的意思是只要还有没被排除的位置就继续搜索。注意这里是小于等于不是小于因为当left和right相等时当前这个位置可能是答案不能跳过。比较之后如果arr[mid] target说明目标值一定在mid的右边而且mid本身也已经比较过了不会等于target所以left直接跳到mid 1。反过来如果arr[mid] target说明目标值在mid左边right跳到mid - 1。left (right - left) / 2保证每次mid都落在当前区间靠左的中间位置。整个循环结束时说明有效区间已经空了目标不存在返回-1。2.4 为什么是right mid - 1而不是right mid在闭区间下最容易卡住的一个点是为什么比较完arr[mid]之后更新右边界要用right mid - 1而不是right mid。道理其实一句话就能讲明白arr[mid]已经和target比较过了我们已经知道它不等于target所以这个位置没有保留价值下一次的搜索区间应该把它排除在外。假如写成right mid那么下一轮循环又会把mid包含进来再做一次重复的比较区间没有真正缩小到只剩未知区域还可能在区间长度为2时陷入死循环。用一个生活类比你挨个敲房间的门找人敲开某间门发现里面没人那你接下来找的范围必然是从这扇门之后的区域继续而不是再从这间房开始。算法里的每次比较就是一次敲门已经确认过的位置没必要再敲一遍。3. 二分查找的边界翻车现场四个典型错误排查3.1 循环条件写成left right最后一个元素被漏掉第一类高频错误是把while (left right)写成while (left right)。你别小看这个等号它决定了最后一轮循环还能不能执行。举个例子数组{1, 3, 5}目标值是1。正确的闭区间流程是left0right2mid1arr[1]3比1大于是right0。此时left和right都等于0目标值在下标0的位置。如果循环条件是left right当left等于right时循环直接结束返回-1可目标值明明就在下标0答案就错了。问题的本质在于当leftright时区间里还剩最后一个位置没有检查这个位置可能就是答案。所以写闭区间二分时循环条件必须是。每次写完代码建议你自己沿着一个小数组手动走一遍看看最后剩一个元素时循环是否还在运行。这个习惯比记任何口诀都管用。3.2 指针更新写成left mid死循环是怎么来的第二类高频错误是更新指针时忘了加1或减1。典型写法是if (arr[mid] target) { left mid; // 错误写法 }看个具体例子数组{1, 3, 5}目标值是5。第一轮left0right2mid1arr[1]3小于5于是left被更新为mid也就是1。下一轮计算mid 1 (2 - 1) / 2 1又是下标1比较结果还是小于left还是1。整个过程区间一直是[1, 2]不会再缩小循环永远跑不出去。死循环的根源是当中点落在区间左侧向下取整时left mid没有让左边界前进。修复方法就是前面说的已经比较过的mid要排除掉所以必须是left mid 1。这个错误很隐蔽因为只写对了一次指针没写对另一次程序不会立刻抛异常而是让进程卡死。调试时最直接的方式是在while循环开头打印left、mid、right三个值看到某个变量连续几轮不变基本就是指针更新写错了。3.3 中点溢出(left right) / 2会在什么时候出问题有人会反驳我写(left right) / 2也没出过错啊。这确实教学例子里数组长度通常很小left和right之和远不到int上限大概率一辈子都跑不出溢出。但算法代码有个习惯是要面向极端输入写而不是面向测试用例写。假设left是15亿right是15亿两个数相加就是30亿超过int最大值结果变成负数mid变成负数arr[mid]直接抛越界。有人可能觉得数组哪可能那么大可这是算法基本功养成防溢出的写法几乎不增加任何成本。真正工作之后你面对的数据可能是几十亿条日志里的某个区间位置也可能是参与运算的两个接近边界的索引值到那时候再改就晚了。早点养成写left (right - left) / 2的习惯是二分查找练习里性价比最高的一件事。3.4 返回值语义没想清楚找不到到底返回什么最后一个容易踩的坑是返回值语义不统一。标准二分查找的约定是找到返回下标找不到返回-1。这个约定本身很清晰很多人栽在把二分查找改一改去解决别的题目时没有重新定义返回值。最典型的是搜索插入位置这类问题如果数组里有目标值返回下标如果没有返回目标值应该被插入的位置让插入后数组仍然有序。这时候如果照搬标准二分最后不假思索地return -1就会直接答错。正确做法是return left因为循环结束后left指向的位置就是第一个不小于target的位置也就是插入点。所以在写任何二分变体之前先问自己一个问题这个函数找不到目标时我希望调用方拿到什么结果把返回值语义想清楚比代码本身更重要。4. 重复元素与插入位置容易被追问的几个变体4.1 找左边界等于目标时也不急着返回基础二分写顺之后下一个要面对的问题是重复元素。比如数组{1, 2, 3, 3, 3, 4, 5}目标值是3。基础二分走到某个下标3就返回了但业务可能要的是第一个等于3的位置也就是下标2。思路很简单当arr[mid]等于target时不返回而是把右边界往左收继续在左半段找是不是还有更靠前的等于target的位置。代码可以这样写public static int findLeftBound(int[] arr, int target) { int left 0; int right arr.length - 1; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { right mid - 1; } else { left mid 1; } } if (left arr.length arr[left] target) { return left; } return -1; }这个写法里arr[mid] target这一行是关键等于的时候也把right往左收。循环结束时left指向第一个大于等于target的位置。最后再做一次检查确认这个位置真的等于target否则表示数组里没有target。整个思路可以概括为找最左边界就是在等于target时继续向左压缩搜索区间。4.2 找右边界对称地调整而不是背另一套代码找最右边界和找最左边界是对称的。区别只在比较逻辑当arr[mid]等于target时不返回而是把左边界往右收继续看右边还有没有等于target的位置。代码如下public static int findRightBound(int[] arr, int target) { int left 0; int right arr.length - 1; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { left mid 1; } else { right mid - 1; } } if (right 0 arr[right] target) { return right; } return -1; }这里的核心动作是arr[mid] target时left往右移动让搜索结果不断向右边界靠拢。循环结束时right指向最后一个小于等于target的位置再确认它等于target就是最右下标。你没必要把两个模板硬背下来只需要记住一句话找左边等于时收右边界找右边等于时收左边界。剩下全是标准二分的骨架。4.3 搜索插入位置为什么最终答案是left在线题库里有一道很经典的题叫搜索插入位置给定一个升序数组和一个目标值如果在数组里能找到就返回下标找不到就返回它按顺序被插入的位置。如果沿用标准二分模板只需要把最后的return -1改成return leftpublic static int searchInsert(int[] arr, int target) { int left 0; int right arr.length - 1; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { return mid; } else if (arr[mid] target) { left mid 1; } else { right mid - 1; } } return left; }为什么left就是插入位置因为当循环结束时区间[left, right]已经为空且所有小于target的值都在left左边所有大于等于target的值都在left及右边。换句话说left左边的元素都小于targetleft及其右边的元素都不小于target那么把target放到下标left数组依然有序。这个结论不需要背手动跑几个例子就能理解。4.4 四个模板的对比与记忆方法场景相等时的动作循环结束时返回标准二分任意一个目标下标直接返回mid找不到返回-1最左边界right mid - 1left需检查arr[left] target最右边界left mid 1right需检查arr[right] target搜索插入位置直接返回midleft不需要额外检查记的时候不用死记整段代码只需要盯住等于那一行。标准二分等于时直接停左右边界等于时继续压缩一侧。这四个模板都来自同一个骨架差别就一两个条件。我练下来的经验是把这四个场景分别手写两遍比看十遍讲解都管用。5. 工程现场的真实用法标准库与答案区间二分5.1 Java标准库里的二分查找Arrays.binarySearch的返回值陷阱业务代码里一般不需要自己写二分Java标准库已经提供了现成实现。Arrays.binarySearch(int[] a, int key)和Collections.binarySearch(List, key)分别针对数组和列表。直接调用当然没问题但标准库的返回值有个容易踩坑的约定找到时返回目标值的下标这个好理解。找不到时返回的不是-1而是-(插入点) - 1。什么叫插入点就是如果要把target插入数组应该放的那个下标。举个例子import java.util.Arrays; public class BinarySearchLibDemo { public static void main(String[] args) { int[] arr {2, 4, 6, 8}; int index Arrays.binarySearch(arr, 5); System.out.println(index); // -3 int insertPos -index - 1; System.out.println(insertPos); // 2 } }返回值-3表示插入点是2也就是下标2的位置应该放5因为下标0、1分别是2和4。如果不知道这个约定拿到负数就直接当作没找到很容易丢掉它应该插在哪这个很有价值的信息。手动计算插入点时用-index - 1就好。5.2 值域二分在答案的取值范围里做搜索二进制查找不一定只能用在数组下标上。有一类非常实用的问题二分的是答案本身的取值范围。最经典的例子是求一个非负整数的平方根整数部分。假设要求根号x向下取整x是非负整数。已知答案一定在0到x之间而且这个范围是单调的——如果mid的平方小于等于x说明mid可能还不够大如果大于x说明mid太大了。接下来就可以在[0, x]上做二分public static int mySqrt(int x) { int left 0; int right x; while (left right) { int mid left (right - left) / 2; long square (long) mid * mid; if (square x) { left mid 1; } else { right mid - 1; } } return left - 1; }这段代码写在x8上手动跑一遍left0right8mid44×416大于8right3mid11≤8left2mid24≤8left3mid39大于8right2循环结束返回left - 1 2正确。这里把mid强制转成long再乘是为了防止mid接近46340时mid×mid超过int范围。值域二分在工程里很常见比如让最大值最小化的最优化问题、浮点数精度逼近本质都是把答案当作搜索目标。5.3 适用条件自查数组、有序、随机访问最后聊一下二分查找在工程里的适用边界。它有三个硬性条件数据存储在有随机访问能力的位置典型是数组数据必须有序多次查询时优势才明显。为什么数组很重要因为mid拿到之后要立刻读取arr[mid]数组是O(1)随机访问。如果换成链表虽然链表也可以有序但取mid需要从头遍历过去一次比较O(n)二分查找整个退化到O(n log n)还不如线性扫描。所以工程里有序链表要找得快会用跳表这类额外结构而不是硬套二分。数据规模也要权衡。二分查找O(log n)确实快但如果数据就几十个元素直接线性扫描可能还更快因为二分查找里有数组访问、比较、分支跳转这些额外开销。相反如果有一批数据要做很多次查找先排序一次O(n log n)再用二分做多次O(log n)查询通常比每次线性扫描划算得多。选择算法不是比谁代码短而是算清楚数据规模和访问模式下的整体成本。我在实际学习中的体会是二分查找是最典型的一听就懂、一写就错的算法。它错不在循环错在写代码前没有先定义清楚区间到底是什么。后来我养成一个习惯每次写二分相关代码之前先在注释里写一行当前区间[left, right]表示目标可能存在的范围再开始写循环。这个习惯帮我少踩了无数坑。如果你现在刚开始Java学习建议每天花二十分钟把标准实现、左右边界变体各手写一遍连续三天之后遇到任何在有序数据里找边界的问题都会比别人快一步。