开头聊到二分查找Binary Search很多人的第一反应是“这不就是面试必考的基础题吗”但真正能一次写对的人其实很少。这个算法核心思想说来就一句话——在一个有序数组里每次拿中间值和目标比较把搜索范围砍掉一半直到找到目标或者范围为空。它的时间复杂度稳定在 O(log n)也就是说一百万条数据最多比较二十次就能定位到结果这种效率在线性扫描面前是碾压性的。用 Java 实现二分查找不光是为了应付面试实际工程里也到处是它的影子。比如数据库索引的 B 树查找、磁盘上的二分定位、游戏排行榜的分数排名查询底层都离不开这种减而治之的思想。这篇我把二分查找的原理、边界处理、不同写法之间的取舍、以及新手最容易踩的坑一次性讲透适合正在学算法的人、准备跳槽刷题的人以及想扎实补基础的后端开发。看完你不仅能写出“能用”的二分查找还能写出“无懈可击”的版本。1. 内容整体设计与思路拆解1.1 为什么二分查找是一种“思路简单、实现极难”的算法先说个有意思的现象。很多刚学编程的人看二分查找的原理五分钟就点头说懂了——不就是拿中间值和目标比大小嘛。但让他们自己手写一版写出来的代码大概率是错的而且错得千奇百怪。边界条件写错、死循环、数组越界、漏掉第一个或最后一个元素这些问题在面试和实际开发中都太常见了。问题出在哪因为二分查找真正考验的并不是“理解算法”这个层面而是你对“区间”这个抽象概念的把握。数组的下标区间是一个半开半闭还是全闭的区间直接决定了循环条件怎么写、左右指针怎么移动。差一个等号结果就可能天差地别。我把这种差别叫做“二分查找的灵魂三问”循环里到底要不要加等号左指针要不要加一右指针要不要减一这三个问题想不清楚代码写出来就一定是碰运气。我从一开始写二分查找的时候也犯过迷糊后来总结出一个靠谱的思路写之前先在纸上明确自己用的是哪种区间定义然后在代码里把所有条件都按这个定义来推导。不要一会儿用闭区间一会儿用开区间那是灾难的源头。这是整个设计层面的第一原则——一致性。1.2 适用前提有序性、随机访问和单调性二分查找不是万能的。很多人在实际业务里用错它是因为忽略了它的三个前提条件。第一个是有序性。二分查找依赖“顺序”来做判断如果数组没有排序mid 位置的元素无法告诉我们目标是在左侧还是右侧算法直接失效。所以用任何二分查找之前第一件事就是确认数据已排序。如果数据频繁变动、每次都要重新排序那二分查找的收益就会被排序成本吃掉这时候哈希表或者平衡树可能更合适。第二个是随机访问能力。二分查找需要快速拿到数组中间位置的值这要求数据结构支持 O(1) 的按下标访问。Java 的数组、ArrayList 都满足这个要求但链表不满足。如果你拿一个 LinkedList 去实现二分查找每次“取中间元素”都要从头遍历复杂度直接退化成 O(n log n)还不如做一遍线性扫描。第三个是单调性或者说“排好序的区间具备可预测性”。这点听起来和第一点一样但其实是想强调一种场景二分查找不仅可以用在数组上还可以用在“答案的单调区间”上。举个例子你的程序要在一堆时间戳中找到第一个大于某个时间点的记录这本质上就是在一个单调递增的时间轴上做二分。理解了这层你会发现二分查找的应用面比想象中大得多它甚至不用真的有一个“数组”——只要你能定义出一个单调的搜索空间就行。1.3 自己实现还是直接用 Arrays.binarySearchJava 标准库其实自带了一个二分查找工具就是java.util.Arrays.binarySearch(int[] a, int key)。很多人问我既然 JDK 有了为什么还要自己写我的回答是在业务代码里能用标准库就应该用标准库它经过了充分测试边界处理也更严格。但有三种情况你仍然需要自己实现或理解原理。第一种是标准库版本的行为不完全符合需求比如它找不到目标时返回的是一个负数-(insertionPoint) - 1很多人记不住这个规律容易用错第二种是面试场景面试官让你“手撕”一个正确的二分查找第三种是标准库只支持精确查找不支持“第一个大于等于目标的元素”这类变体这种场景需要自己写lowerBound和upperBound。我建议的学习路径是先自己写清楚基础版本和几个变体理解底层逻辑然后在生产代码里优先用标准库。这样既保证了代码质量又能在标准库不够用的时候从容地自己顶上。2. 核心细节解析与实操要点2.1 循环不变量写出正确二分的关键很多人写二分查找靠的是“背模板”——记住while (left right)记住left mid 1但一旦目标变成查找左边界、右边界模板就失灵了。原因就是没有理解藏在代码背后的核心概念循环不变量。循环不变量说直白一点就是“在每轮循环开始的时候你能确定目标值在哪个区间里”。这个区间就是你用左右指针维护的那个范围。只要你在代码里始终维护这个范围的有效性算法就一定正确如果你破坏了它比如把左指针直接移到mid而mid已经被排除在候选区间之外那就会出问题。我用一个很生活化的比方来解释。你在一个书架前找一本书书是按照编号从小到大排的。你每次抽出一本中间的书看它的编号如果比目标书大你就把右边一半书排除掉如果比目标书小你排除左边一半。这里的“排除”有两种做法一种是彻底把它拿开也就是left mid 1另一种是只把它当作“分界线”保留在区间里也就是left mid。这两种做法对应了不同的区间定义和不同的边界处理方式。只要你在写代码之前明确回答一个问题“我维护的区间到底是包含答案的闭区间还是包含答案但不包含右端点的半开区间”然后让每一步操作都符合这个区间定义二分查找就不可能写错。这就是循环不变量的意义——它像是一条线索贯穿了算法的全部逻辑。2.2 左闭右闭与左闭右开两种主流区间定义实际写代码时最常见的是两种区间定义方式我先各说清楚一种。第一种是左闭右闭也就是区间[left, right]包含两个端点。在这种定义下每次循环开始时目标值如果存在必然在left到right的范围内。循环条件天然就是while (left right)因为当left right时区间里还有一个元素不能直接退出。计算mid之后如果nums[mid]大于目标说明mid及其右侧都可以排除所以right mid - 1如果nums[mid]小于目标说明mid及其左侧都可以排除所以left mid 1如果相等直接返回。第二种是左闭右开也就是区间[left, right)包含左端点、不包含右端点。我不得不说这种定义在不少优秀的开源代码里更常见因为它和数组遍历的很多习惯一致在一个范围为空时left right也更好判断。循环条件要写成while (left right)因为当left right时区间已经没有元素了。此时如果nums[mid]大于目标right mid——注意这里不是mid - 1因为右端点是开区间mid本身虽然已经不在候选范围里但实际上right指向的位置我们不检查所以把right设为mid就相当于排除了mid及右侧所有元素如果nums[mid]小于目标left mid 1因为左端点是闭区间mid本身必须被排除。你看两种定义只在细节上差了一点点但如果混着用比如左闭右开却写right mid - 1就会漏掉元素。我强烈建议初学者先只掌握一种把它练熟再理解另一种不要一开始就试图融合两种写法。2.3 防止整数溢出mid 的计算暗藏玄机二分查找里最容易忽略的细节之一是mid的计算方式。很多教科书上写的是int mid (left right) / 2这个写法在数组长度不大的时候确实没问题但当left和right都是接近Integer.MAX_VALUE的大数时left right会直接溢出变成一个负数。Java 里整数溢出后(负数) / 2的结果就完全错误了程序可能直接访问到负下标抛出数组越界异常。正确的标准写法是int mid left (right - left) / 2。这个公式避免了left right的加法溢出因为right - left不会超过整个数组的长度。另一种写法是利用无符号右移int mid (left right) 1在 Java 中会先把两个数相加的结果当作无符号整数来处理因此也能规避溢出问题。我个人在实际开发中更习惯用前一种写法因为它不需要额外记忆“无符号右移”的语义对后来读代码的人也更友好。2.4 递归版与迭代版怎么选二分查找有两种常见实现形式递归和迭代。我给一个直观的对比表格维度递归版迭代版代码可读性逻辑直观和数学归纳法对应稍显繁琐但结构清晰栈空间开销每次递归会压栈深度 O(log n)只用几个变量无额外栈开销性能表现递归调用有额外开销但差距很小理论上更快适合高频调用场景调试难度调用栈能帮你跟踪递归过程需要自己维护指针变化适用场景学习理解、递归思维训练生产代码、标准库实现我个人的建议是学习阶段两种都写一遍理解各自的优劣实际工程里优先用迭代版因为它的空间复杂度是 O(1)也不容易出现栈溢出问题。虽然二分查找的递归深度只有 O(log n)对这种量级的栈开销并不敏感但如果把二分查找嵌入到一个本身递归就很深的算法里叠加起来就可能出问题。节省每一位操盘手都需要注意的成本是我们的职业素养。3. 实操过程与核心环节实现3.1 基础版标准二分查找的完整 Java 实现说了这么多理论该动手了。我用左闭右闭的区间定义给出一个最标准的迭代版二分查找实现。/** * 在有序数组 nums 中查找目标值 target * param nums 升序排列的整型数组 * param target 要查找的目标值 * return 目标值的下标如果不存在返回 -1 */ public static int binarySearch(int[] nums, int target) { // 定义搜索区间为 [left, right]初始是整个数组 int left 0; int right nums.length - 1; // 当 left right 时区间为空搜索结束 while (left right) { // 防止溢出等价于 (left right) / 2 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; // 没有找到 }这段代码的核心要点有两个。第一while (left right)的等号不能丢因为当left right时区间里还剩最后一个元素这个元素可能就是目标第二收缩时left mid 1和right mid - 1都把已经检查过的mid排除掉了这就保证每次循环搜索范围严格缩小最终一定能退出。你可以用一个例子来验证逻辑。比如数组[1, 3, 5, 7, 9]目标值是7。第一步left0、right4mid2nums[2]55 比 7 小于是left3第二步left3、right4mid3nums[3]7命中返回 3。整个过程只比较了两次。如果是线性扫描要比较四次。数组越大这个优势越明显。3.2 递归版实现换个角度看减而治之递归版代码逻辑和迭代版是一样的只是把循环换成了函数调用。我用它来解释“减而治之”非常合适因为每次递归都把问题规模缩小一半。public static int binarySearchRecursive(int[] nums, int target) { return search(nums, target, 0, nums.length - 1); } private static int search(int[] nums, int target, int left, int right) { // 递归终止条件区间为空目标不存在 if (left right) { return -1; } int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { // 目标可能在右半部分 return search(nums, target, mid 1, right); } else { // 目标可能在左半部分 return search(nums, target, left, mid - 1); } }如果说迭代版是“用一个循环遍历收缩”递归版就是“用函数调用表达递归关系”。这段代码的终止条件left right对应着迭代版的while (left right)退出条件。对初学者来说递归版更容易和“分治”的思想对上因为你是站在一个更宏观的视角来表达逻辑。微妙的区别在于每次递归都会创建新的栈帧虽然二分查找的深度很低但你在阅读别人的代码时如果能快速把递归版转换为迭代版说明你对这个算法的理解是真的到位了。3.3 查找左边界第一个等于目标值的位置实际业务里精确查找一个值往往不够用。比如你要处理一批带时间戳的记录需要找到“第一个时间大于等于某个阈值的记录”这就是查找左边界。我把这种变体称为lowerBound它返回的是第一个满足nums[i] target的下标。/** * 在升序数组中找到第一个 target 的下标 * 如果所有元素都小于 target返回 nums.length */ public static int lowerBound(int[] nums, int target) { int left 0; int right nums.length; // 注意这里用 nums.length而不是 nums.length - 1 while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { right mid; // 命中或 mid 值偏大收缩右边界 } else { left mid 1; // mid 值太小收缩左边界 } } return left; }注意这个写法和基础版的区别右边界初始值是nums.length而不是nums.length - 1这意味着我们维护的是一个左闭右开的区间[left, right)。这个设计是有意的因为lowerBound有可能返回nums.length表示“数组中所有元素都小于目标”这时候返回值本身就是数组末尾的下一个位置。如果你用nums.length - 1初始化右边界就逼着自己在代码里额外处理“全小于”的情况逻辑会变得很别扭。这个版本还有一个特点当nums[mid] target时我们并不会立即返回mid而是继续把right收缩到mid。这是因为可能有多个值和 target 相等我们要找的是最左边的那个。收缩到mid之后后续循环会继续向左寻找更小的合法下标直到区间收敛到第一个不小于 target 的位置。理解了这一点你就能理解为什么说二分查找的变体其实是在“搜索区间内找一个极值”。3.4 查找右边界最后一个等于目标值的位置既然有左边界自然有右边界。它和lowerBound是对称的我可以用一个很简单的技巧实现先写upperBound也就是第一个 target的下标然后upperBound - 1就是最后一个 target的下标。/** * 在升序数组中找到第一个 target 的下标 * 如果所有元素都小于等于 target返回 nums.length */ public static int upperBound(int[] nums, int target) { int left 0; int right nums.length; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { right mid; // mid 值偏大收缩右边界 } else { left mid 1; // mid 值小于等于 target收缩左边界 } } return left; } // 查找最后一个等于 target 的下标 public static int lastEqual(int[] nums, int target) { int firstGreater upperBound(nums, target); if (firstGreater 0) { return -1; // 数组第一个元素就大于 target说明不存在 } return nums[firstGreater - 1] target ? firstGreater - 1 : -1; }这里的关键在于upperBound返回的是第一个大于 target 的下标所以如果数组里存在 target那么firstGreater - 1一定是指向最后一个等于 target 的元素的位置。这种“用基础变体组合出高级变体”的思路在实际工程里特别实用——你不需要为每个场景都手写独立的二分逻辑只要把lowerBound和upperBound写对很多问题都能直接套公式解决。顺带补充一个实际开发技巧如果你想在一个有序数组里统计某个值的出现次数比如统计分数段人数或记录重复次数可以直接用upperBound(nums, target) - lowerBound(nums, target)一步算出来。这个思路我在处理数据统计任务时经常用比自己加一堆 if 判断可靠得多。3.5 测试用例边界条件必须全覆盖代码写出来必须经过验证。二分查找的测试我最关注这些边界场景目标值在数组最左侧、在数组最右侧、不存在且落在最小值左侧、不存在且落在最大值右侧、数组中只有一个元素、数组中所有元素都相同。任何一个场景考虑不到都可能在生产环境里踩坑。public static void main(String[] args) { int[] nums1 {1, 3, 5, 7, 9}; System.out.println(binarySearch(nums1, 7)); // 期望 3 System.out.println(binarySearch(nums1, 1)); // 期望 0 System.out.println(binarySearch(nums1, 9)); // 期望 4 System.out.println(binarySearch(nums1, 0)); // 期望 -1 System.out.println(binarySearch(nums1, 10)); // 期望 -1 int[] nums2 {5, 5, 5, 5, 5}; System.out.println(lowerBound(nums2, 5)); // 期望 0 System.out.println(upperBound(nums2, 5)); // 期望 5 int[] nums3 {1, 2, 2, 2, 3, 4}; System.out.println(lastEqual(nums3, 2)); // 期望 3 System.out.println(lowerBound(nums3, 2)); // 期望 1 }你可以在本地跑一下这些用例把输出和期望一一对照。如果全对说明你对二分查找的边界理解已经到位了。千万别觉得写测试浪费时间二分查找这种算法恰恰是最需要用测试用例来证明自己正确性的类型。4. 常见问题与排查技巧实录4.1 死循环是怎么产生的死循环是二分查找新手最常遇到的问题。它的根源只有一个搜索区间没有严格缩小导致left和right一直原地打转。一个典型的错误写法是在区间[left, right]的定义下当nums[mid] target时把left设成了mid而不是mid 1。这样当数组只有两个元素时比如left0、right1mid0如果目标值确实在右半区left仍然等于 0新区间还是[0, 1]下一轮循环又是同样的结果无限循环就发生了。我在排查这样的问题时会做一个非常机械的操作手里拿一张纸把每一轮循环中left、right、mid的值都记下来。只要写出来你就会发现区间没有收敛的趋势。这是一种笨办法但非常有效。遇到死循环别慌画出指针变化图通常一眼就能看出问题。这个问题的根治方案很简单收缩时永远把mid排除在新区间之外。在左闭右闭区间里就是left mid 1和right mid - 1在左闭右开区间里就是left mid 1和right mid。只要严格执行这个原则死循环不可能发生。4.2 边界处理错误导致漏元素第二个常见问题是漏掉目标元素。症状表现为数组里明明有目标值但二分查找返回了-1。最常见的原因是把while (left right)写成了while (left right)。在左闭右闭区间里当left right时区间里还有一个元素未检查你如果让它直接跳出循环这个元素就被漏掉了。比如数组[5]查找5初始left0、right0如果循环条件没有等号根本进不去循环体直接返回-1。另一种漏元素的原因是右指针初始值写错。如果数组长度为n在左闭右闭区间里right应该是n - 1如果你写成n那第一次取mid之后可能在nums[n]处越界或者压根访问不到最后一个元素。这个问题在 Java 中会表现为ArrayIndexOutOfBoundsException在 C/C 里则可能是静默的越界读。无论哪种排查时先检查一下你的初始区间是否覆盖了整个数组。4.3 数组未排序导致结果全错这个问题很隐蔽。数组没排序二分查找结果不正确但程序不会报错表现就是结果忽对忽错非常难排查。我之前处理过一个真实案例某个模块里对一份数据源做二分查找偶尔查不到目标后来发现是上游数据在传递时有一步没有正确排序导致输入数组在整体上乱序。从方法论上我会建议任何使用二分查找的地方至少在调试阶段加一个前置校验确认数组是有序的。在生产环境里做这种校验可能影响性能但你可以选择在测试环境开启。有一个低成本的做法是在写单元测试时多生成几组随机数组排序后跑二分查找再和线性扫描的结果比对。如果二分查找结果和线性扫描不一致问题多半不在二分查找本身而在输入数据是否真的有序。4.4 用 Arrays.binarySearch 时的注意点有些读者会用标准库的Arrays.binarySearch来偷懒这也是可以的但有几个细节我提醒过很多次了。第一找不到元素时返回的是负数-(insertionPoint) - 1这个insertionPoint指的是如果要把目标插入数组应该插入的位置。很多人以为没找到就返回-1结果拿返回值直接当下标用程序直接崩溃。第二它要求数组必须先排序否则结果是未定义的注意是未定义——也就是说下次运行可能得到不同结果。第三如果数组里有多个相同元素标准库不保证返回哪一个下标你需要时还得自己写lowerBound和upperBound。我把常见问题整理成一张速查表方便你排查时对照症状可能原因排查建议死循环收缩时使用了left mid且区间未缩小画指针变化图确认新区间是否严格缩小返回 -1 但目标存在循环条件少了等号或右指针初始值错误检查while条件是否为右指针是否为n-1数组越界mid计算溢出或初始区间错误改用left (right - left) / 2检查左右指针初始值结果时对时错输入数组未排序测试环境中校验输入有序性与线性扫描对比标准库返回负数下标未处理-(insertionPoint) - 1语义判断返回值小于 0 时不要直接当下标使用重复元素时结果不确定二分查找不保证重复元素返回位置需要固定位置时使用lowerBound或upperBound4.5 调试二分查找的小技巧最后分享几个我实际调试二分查找时很受用的小技巧。第一个是“打印指针”。在循环开头加一行临时的System.out.println(left left , right right , mid mid)跑一个小例子立刻就能看清算法是怎么收敛的。问题代码往往在第一轮循环就能暴露出指针移动方向的错误。第二个是“最小用例归约”。遇到二分查找相关的问题我先构造一个长度为 2 的数组[a, b]再构造一个长度为 1 的数组[a]在这些最小用例上跑代码。如果有错大多会在这两个简单例子上暴露出来比用十万个元素的用例好查一百倍。长度 1 的场景尤其能暴露循环条件错误。第三个是“随机对照测试”。写一个辅助方法把二分查找和线性扫描的结果做对比随机生成几百组数据跑一遍全部一致才放心。这个方法在改动算法变体时特别有用因为变体之间差一点点就可能导致行为不同。我每次写完一个二分查找变体都会跑对照测试来验证正确性这比我人眼检查可靠得多。结尾收个尾我在实际学习和工作中反复写过很多次二分查找最大的体会是这个算法看起来小但它逼着你去思考“循环不变量”和“区间定义”这些底层概念一旦想清楚了后面学快排、学归并、学各种分治算法都会轻松不少。它像是算法世界里的一块敲门砖同时也是检验你思维缜密度的试金石。如果你刚开始接触我建议不要只抄代码而是拿起笔手动模拟一遍[1, 3, 5, 7, 9]查7的过程。把每个left、right、mid的值都写下来你会发现算法运转的内在逻辑非常清晰。之后再试着改一下条件比如把left right改成left right手动跑一遍看看会发生什么。这种“故意破坏再修复”的实验比背十遍模板都有用。最后再分享一个小技巧写二分查找变体时别急着一步到位。先用最熟悉的左闭右闭区间写出基础版本跑通测试再改造成lowerBound或upperBound。小步快跑每次只改一个条件每一步都跑测试这样出错时你永远知道是哪一步改出的问题。二分查找不难难的是每次都带着清晰的头脑去写代码——保持这种习惯你会发现它其实非常优雅。