引言在算法的世界里二分查找Binary Search是一个看似简单却内涵极其丰富的算法。它不仅是数据结构与算法领域的入门经典更是无数高级算法如快速幂、牛顿迭代、三分查找、动态规划优化中的决策单调性等的基础。如果说线性查找是“笨拙的试探”那么二分查找就是“智慧的跳跃”。它利用数据的有序性每次都将搜索范围缩小一半从而将线性时间复杂度的查找问题优化到对数级别。本文将全面、深入、系统地总结二分查找算法从核心思想出发涵盖各种变体、边界处理、易错点、应用场景以及思维升华力求帮助读者建立起对二分查找的深刻理解。第一部分核心思想与基本原理1.1 算法定义二分查找又称折半查找是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始如果中间元素正好是要查找的元素则搜索过程结束如果某一特定元素大于或者小于中间元素则在数组大于或小于中间元素的那一半中查找而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空则代表找不到。1.2 核心思想分而治之二分查找的核心思想是分治Divide and Conquer的典型应用。它将一个规模为 $n$ 的问题通过一次比较转化为一个规模为 $n/2$ 的子问题从而将时间复杂度从 $O(n)$ 降为 $O(\log n)$。这种思想可以用一个生动的例子来说明猜数字游戏。主持人心中想一个1到100之间的整数参与者每次猜一个数主持人告诉他是猜大了还是猜小了。最优策略就是每次猜中间的数。第一次猜50如果大了范围缩小到1-49如果小了范围缩小到51-100。如此反复最多7次因为 $2^7128 100$就能猜中。1.3 适用条件二分查找并非万能它的应用需要满足以下两个基本条件有序性数据必须是有序的单调递增或单调递减。这是二分查找能“舍弃一半”的依据。如果数据无序则无法判断目标元素在左半部分还是右半部分。随机访问数据结构必须支持高效的随机访问。通常要求底层数据结构是数组或类似于数组的线性表这样才能在 $O(1)$ 时间内访问任意索引的元素。链表虽然有序但无法高效地定位中间节点因此不适合直接使用二分查找。1.4 算法流程二分查找的经典流程可以用一个伪代码清晰地表示textfunction binarySearch(nums, target): left 0 right nums.length - 1 // 初始化左右边界 while left right: // 当搜索区间不为空时 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 // 未找到目标1.5 为什么是 $\log n$假设数组长度为 $n$每次查找后搜索范围缩小为原来的一半。最坏情况下需要查找的次数 $k$ 满足n×(12)k≈1n×(21​)k≈1即n≈2kn≈2kklog⁡2nklog2​n因此二分查找的时间复杂度为 $O(\log n)$。这意味着当 $n 10^9$ 时$\log_2 n \approx 30$只需要约30次比较效率极高。第二部分二分查找的经典模板二分查找的实现细节非常微妙尤其是边界条件left和right的初始值、循环条件、mid的更新方式稍有不同就会导致错误或死循环。因此掌握几种经典的模板至关重要。2.1 模板一标准二分查找查找精确值这是最基本的二分查找用于在一个无重复元素的有序数组中查找一个特定值找到即返回索引找不到则返回 -1。代码实现javaint binarySearch(int[] nums, int target) { int left 0; int right nums.length - 1; // 注意右边界是闭区间 [left, right] while (left right) { // 当 left right 时区间仍然有效 int mid left (right - left) / 2; // 防止 (leftright) 溢出 if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; // target 在右侧排除 mid } else { right mid - 1; // target 在左侧排除 mid } } return -1; }关键点解析区间定义我们定义搜索区间为闭区间 $[left, right]$即left和right都包含在搜索范围内。循环条件left right。当left right时区间内还有一个元素需要继续检查。如果使用left right则会漏掉这个元素。mid计算left (right - left) / 2等同于(left right) / 2但能有效避免整数溢出。边界更新由于mid已经检查过且不符合条件所以更新时跳过mid即left mid 1或right mid - 1。2.2 模板二查找左边界第一个等于 target 的位置当数组中存在重复元素时我们可能需要找到目标值第一次出现的位置左边界或最后一次出现的位置右边界。左边界查找的典型场景是lower_bound函数。代码实现javaint leftBound(int[] nums, int target) { int left 0; int right nums.length; // 注意右边界是开区间 [left, right) while (left right) { // 当 left right 时区间为空停止 int mid left (right - left) / 2; if (nums[mid] target) { right mid; // 找到 target收缩右边界继续向左搜索 } else if (nums[mid] target) { left mid 1; // target 在右侧 } else { right mid; // target 在左侧mid 不可能是答案但右边界开区间特性让 right mid } } // 检查 left 是否越界以及 nums[left] 是否等于 target if (left nums.length || nums[left] ! target) { return -1; } return left; }关键点解析区间定义这里采用了左闭右开区间 $[left, right)$。这是 C STL 中lower_bound的常见风格使得边界处理更加简洁。循环条件left right。当left right时区间为空搜索结束。mid计算同样使用防溢出写法。边界更新当nums[mid] target时我们想找到最左边的 target因此不能立即返回而是将right设为mid缩小右边界继续在左侧搜索。当nums[mid] target时说明目标在右侧left更新为mid 1因为mid已被排除。当nums[mid] target时说明目标在左侧right更新为mid由于右边界是开区间mid不会被包含在下一次搜索中。循环结束后left指向的是第一个大于等于 target 的位置。我们需要检查该位置是否越界以及值是否等于 target以确定 target 是否存在。2.3 模板三查找右边界最后一个等于 target 的位置右边界查找对应upper_bound的前一个位置。代码实现javaint rightBound(int[] nums, int target) { int left 0; int right nums.length; // 左闭右开区间 [left, right) while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; // 找到 target收缩左边界继续向右搜索 } else if (nums[mid] target) { left mid 1; } else { right mid; } } // 循环结束时left rightleft 指向第一个大于 target 的位置 // 因此最后一个等于 target 的位置是 left - 1 if (left - 1 0 || nums[left - 1] ! target) { return -1; } return left - 1; }关键点解析与左边界查找对称当nums[mid] target时我们向右搜索更新left mid 1。循环结束后left指向第一个大于 target 的元素。因此最后一个等于 target 的索引是left - 1。同样需要进行边界检查和值确认。2.4 模板对比与选择模板区间定义循环条件返回值适用场景标准模板闭区间[left, right]left right找到返回索引否则 -1无重复元素查找精确值左边界模板左闭右开[left, right)left right返回第一个 ≥ target 的索引查找第一次出现的位置、插入位置右边界模板左闭右开[left, right)left right返回最后一个 ≤ target 的索引查找最后一次出现的位置选择建议如果只是简单的查找使用标准模板最直观。如果涉及重复元素的边界问题或者需要实现lower_bound/upper_bound功能建议统一使用左闭右开区间的模板因为它在处理边界时更加统一和健壮。第三部分二分查找的变体与应用二分查找远不止于在有序数组中查找一个数。通过巧妙的转化它可以解决大量看似复杂的问题。3.1 在旋转排序数组中查找问题描述一个升序数组在某个未知点进行了旋转例如[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2]要求在该数组中查找目标值。核心思想虽然整个数组不是全局有序的但旋转后数组被分成了两个分别有序的部分。通过比较nums[mid]和nums[left]或nums[right]可以判断mid位于哪个有序部分从而确定目标在哪一部分。代码实现无重复元素javaint search(int[] nums, int target) { int left 0, right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) return mid; // 判断左半部分是否有序 if (nums[left] nums[mid]) { // 左半部分有序判断 target 是否在左半部分 if (target nums[left] target nums[mid]) { right mid - 1; } else { left mid 1; } } else { // 右半部分有序判断 target 是否在右半部分 if (target nums[mid] target nums[right]) { left mid 1; } else { right mid - 1; } } } return -1; }变体如果数组包含重复元素如[1,1,1,3,1]情况会更复杂。当nums[left] nums[mid]时无法判断哪部分有序此时只能将left右移一步继续搜索。这种场景下最坏时间复杂度可能退化到 $O(n)$。3.2 在二维矩阵中查找问题描述在一个每一行都从左到右递增且每一行的第一个元素都大于上一行最后一个元素的矩阵中查找目标值。核心思想这种矩阵可以视为一个拉直后的一维有序数组。我们可以通过坐标转换直接使用一维二分查找。代码实现javaboolean searchMatrix(int[][] matrix, int target) { if (matrix null || matrix.length 0) return false; int m matrix.length, n matrix[0].length; int left 0, right m * n - 1; while (left right) { int mid left (right - left) / 2; int row mid / n; // 关键将一维索引转换为二维行列 int col mid % n; int val matrix[row][col]; if (val target) return true; else if (val target) left mid 1; else right mid - 1; } return false; }3.3 查找峰值元素问题描述峰值元素是指其值大于左右相邻值的元素。给定一个数组可能有多个峰值要求找到任意一个峰值元素。要求时间复杂度 $O(\log n)$。核心思想虽然数组不是完全有序的但我们可以利用“爬坡”的思想。如果nums[mid] nums[mid1]说明峰值在右侧否则峰值在左侧包括mid本身。代码实现javaint findPeakElement(int[] nums) { int left 0, right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] nums[mid 1]) { left mid 1; // 峰值在右侧 } else { right mid; // 峰值在左侧或就是 mid } } return left; }这个问题的精妙之处在于我们不需要全局有序只需要利用局部单调性就能通过二分查找定位到峰值。3.4 求平方根问题描述实现int sqrt(int x)函数计算并返回 x 的平方根其中 x 是非负整数。要求只保留整数部分。核心思想在区间 $[0, x]$ 上二分查找寻找满足 $mid^2 \le x$ 的最大mid。代码实现javaint mySqrt(int x) { if (x 0) return 0; int left 1, right x; while (left right) { int mid left (right - left) / 2; // 使用 mid x / mid 避免溢出 if (mid x / mid) { if ((mid 1) x / (mid 1)) { return mid; // mid 是答案 } left mid 1; } else { right mid - 1; } } return -1; }这里有一个关键技巧为了避免mid * mid溢出我们使用除法mid x / mid进行比较。3.5 二分答案最大值最小化 / 最小值最大化这是二分查找最强大的应用之一。当问题具有“单调性”时我们可以将求解问题转化为判定问题给定一个猜测值mid判断是否可行然后根据结果调整搜索区间。典型场景在一条直线上放置 K 个点使得相邻点之间的最小距离最大化。将数组分成 M 段使得各段和的最大值最小化。在给定时间内完成所有任务求最小所需资源。通用框架java// 假设我们需要找到满足条件的最小值 int left minPossible, right maxPossible; while (left right) { int mid left (right - left) / 2; if (check(mid)) { // mid 可行尝试更小的值 right mid; } else { // mid 不可行需要更大的值 left mid 1; } } return left;案例分割数组的最大值给定一个非负整数数组nums和一个整数m你需要将这个数组分成m个非空的连续子数组。设计一个算法使得这m个子数组各自和的最大值最小。javaint splitArray(int[] nums, int m) { int left 0, right 0; for (int num : nums) { left Math.max(left, num); // 下界单个元素的最大值 right num; // 上界所有元素的和 } while (left right) { int mid left (right - left) / 2; if (canSplit(nums, m, mid)) { right mid; } else { left mid 1; } } return left; } boolean canSplit(int[] nums, int m, int maxSum) { int count 1; int sum 0; for (int num : nums) { if (sum num maxSum) { count; sum num; if (count m) return false; } else { sum num; } } return true; }第四部分二分查找的复杂度与正确性证明4.1 时间复杂度最好情况$O(1)$第一次比较就找到目标。最坏情况$O(\log n)$每次比较后范围减半直到区间缩小为1。平均情况$O(\log n)$。4.2 空间复杂度迭代实现$O(1)$只使用了常数个辅助变量。递归实现$O(\log n)$递归调用栈的深度为 $\log n$。4.3 正确性证明循环不变式二分查找的正确性可以通过循环不变式Loop Invariant来严格证明。以标准模板为例循环不变式为如果目标值target存在于数组中那么它一定位于区间 $[left, right]$ 内。初始化在循环开始前区间 $[0, n-1]$ 包含了整个数组因此不变式成立。保持在循环体内我们计算mid并与target比较如果nums[mid] target直接返回循环结束。如果nums[mid] target由于数组有序target不可能在mid左侧因此新的区间 $[mid1, right]$ 仍然包含target如果存在。如果nums[mid] target类似地新的区间 $[left, mid-1]$ 仍然包含target。终止当left right时区间为空此时根据不变式target不存在于数组中返回 -1 是合理的。通过循环不变式我们能够确信算法的正确性。第五部分常见误区与调试技巧二分查找虽然思想简单但实现时非常容易出错。以下是几个最常见的误区及应对策略。5.1 误区一死循环现象程序陷入无限循环left和right不再变化。常见原因在left right的循环中当left和right相邻时mid等于left。如果更新时left mid那么区间永远不会缩小。解决方案根据区间类型选择合适的mid计算方式和更新方式。在左闭右开区间中通常使用left mid 1和right mid不会死循环。在查找右边界时如果使用left mid则需要将mid改为left (right - left 1) / 2即向上取整。5.2 误区二边界溢出现象当left和right都很大时(left right) / 2可能导致整数溢出。解决方案始终使用left (right - left) / 2来计算mid。对于负数虽然溢出风险较小但为了代码的健壮性同样推荐这种写法。5.3 误区三索引越界现象访问nums[mid]或nums[left]时索引可能为 -1 或nums.length。解决方案在访问数组元素之前确保索引在有效范围内。在左边界/右边界查找结束后务必检查left或right是否越界。5.4 调试技巧打印中间状态在循环中打印left,right,mid的值观察区间的收缩过程。使用小规模测试用长度为 1、2、3 的数组进行测试覆盖边界情况。统一模板在一段时间内坚持使用一种边界风格如左闭右开直到熟练。画图在纸上画出数组和边界模拟二分过程这对理解边界更新非常有帮助。第六部分二分查找的高级应用与思维升华6.1 函数上的二分查找二分查找不仅适用于数组也适用于任何具有单调性的函数 $f(x)$。如果我们需要找到满足 $f(x) \ge target$ 的最小 $x$且 $f(x)$ 是单调递增的就可以使用二分查找。这在数值计算、优化问题中非常常见。例如求方程 $x^3 x - 1 0$ 的根可以通过二分法逼近。6.2 二分查找与 STL在 C 的标准模板库STL中提供了现成的二分查找函数这些函数是经过高度优化和严格测试的推荐在工程代码中使用。std::lower_bound返回第一个大于等于 value 的迭代器。std::upper_bound返回第一个大于 value 的迭代器。std::binary_search返回 bool 值判断元素是否存在。std::equal_range返回一对迭代器表示 value 出现的范围。了解这些函数的内部实现有助于加深对二分查找的理解。6.3 二分查找的局限性尽管二分查找非常高效但它并非银弹依赖有序结构数据必须有序。如果数据频繁变动插入、删除维护有序的成本可能很高此时平衡二叉搜索树如红黑树可能是更好的选择。不适合链表链表不支持随机访问使用二分查找需要 $O(n)$ 的时间来定位中间节点失去了 $\log n$ 的优势。缓存友好性二分查找的访问模式是跳跃的不如线性扫描对 CPU 缓存友好。对于非常小的数据集如 $n100$线性查找可能比二分查找更快。6.4 思维升华从“查找”到“决策”二分查找的最高境界是将其视为一种决策方法而不仅仅是查找算法。在许多算法问题中我们并不直接查找某个值而是通过二分法来逼近一个最优解。这种思维的核心是将优化问题转化为判定问题。例如“求最大值的最小值” - “给定一个最大值能否满足条件”“求最小值的最大值” - “给定一个最小值能否满足条件”“求最小的可行解” - “给定一个解是否可行”一旦建立了这种转化思维你会发现二分查找的应用范围几乎覆盖了整个算法竞赛和面试中的优化类问题。第七部分二分查找的变种与拓展7.1 三分查找Ternary Search三分查找用于在单峰函数先增后减或先减后增上寻找极值点。它将区间分成三份通过比较两个分点的函数值舍弃一部分区间。虽然三分查找的复杂度也是 $O(\log n)$但它的常数因子比二分查找大且对函数的要求更严格必须是凸函数。通常二分查找的适用范围更广。7.2 指数搜索Exponential Search当数组无限长或长度未知时可以先通过指数级增长的方式确定一个包含目标的上界然后在这个区间内进行二分查找。指数搜索的时间复杂度为 $O(\log n)$在寻找边界时非常高效。7.3 牛顿迭代法牛顿迭代法用于求解方程的根它比二分查找收敛更快平方收敛。对于求平方根等问题牛顿迭代法通常比二分法更高效。javaint mySqrt(int x) { long r x; while (r * r x) { r (r x / r) / 2; } return (int) r; }7.4 二分查找在并查集、线段树中的应用在一些高级数据结构中二分查找常用于加速查询。例如在带权并查集上二分查找某个条件首次满足的位置或在线段树上进行二分查找如找到前缀和大于等于某个值的第一个位置。第八部分经典例题详解为了巩固所学我们挑选几道经典题目进行详细剖析。8.1 LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置题目描述给定一个升序数组和一个目标值找出目标值在数组中的开始位置和结束位置。如果不存在返回[-1, -1]。要求时间复杂度 $O(\log n)$。思路分别使用左边界和右边界查找模板。代码javapublic int[] searchRange(int[] nums, int target) { int left leftBound(nums, target); int right rightBound(nums, target); return new int[]{left, right}; } private int leftBound(int[] nums, int target) { int left 0, right nums.length; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { right mid; } else { left mid 1; } } if (left nums.length nums[left] target) return left; return -1; } private int rightBound(int[] nums, int target) { int left 0, right nums.length; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { right mid; } else { left mid 1; } } if (left - 1 0 nums[left - 1] target) return left - 1; return -1; }8.2 LeetCode 69. x 的平方根题目描述实现int sqrt(int x)函数返回平方根的整数部分。思路在 $[0, x]$ 上二分查找寻找满足 $mid^2 \le x$ 的最大mid。代码javapublic int mySqrt(int x) { if (x 0) return 0; int left 1, right x; while (left right) { int mid left (right - left) / 2; if (mid x / mid) { return mid; } else if (mid x / mid) { left mid 1; } else { right mid - 1; } } return right; }8.3 LeetCode 875. 爱吃香蕉的珂珂题目描述珂珂每小时最多吃 K 根香蕉如果一堆香蕉少于 K 根她会吃完这堆并等待下一小时。给定 piles 数组和 H 小时求能在 H 小时内吃完所有香蕉的最小速度 K。思路典型的最小化最大值问题。对速度 K 进行二分查找速度的下界是 1上界是 max(piles)。判定函数canFinish计算以速度 K 吃完需要的小时数判断是否 ≤ H。代码javapublic int minEatingSpeed(int[] piles, int H) { int left 1, right 0; for (int pile : piles) right Math.max(right, pile); while (left right) { int mid left (right - left) / 2; if (canFinish(piles, H, mid)) { right mid; } else { left mid 1; } } return left; } private boolean canFinish(int[] piles, int H, int speed) { int hours 0; for (int pile : piles) { hours (pile speed - 1) / speed; // 向上取整 } return hours H; }8.4 LeetCode 4. 寻找两个正序数组的中位数题目描述给定两个有序数组nums1和nums2求它们的中位数。要求时间复杂度 $O(\log(mn))$。思路这是二分查找的经典难题。核心思想是在较短的数组上进行二分确定一个分割线使得左半部分的最大值小于等于右半部分的最小值。代码核心思路javapublic double findMedianSortedArrays(int[] nums1, int[] nums2) { if (nums1.length nums2.length) { return findMedianSortedArrays(nums2, nums1); } int m nums1.length, n nums2.length; int totalLeft (m n 1) / 2; int left 0, right m; while (left right) { int i left (right - left 1) / 2; int j totalLeft - i; if (nums1[i-1] nums2[j]) { right i - 1; } else { left i; } } int i left; int j totalLeft - i; int nums1LeftMax (i 0) ? Integer.MIN_VALUE : nums1[i-1]; int nums1RightMin (i m) ? Integer.MAX_VALUE : nums1[i]; int nums2LeftMax (j 0) ? Integer.MIN_VALUE : nums2[j-1]; int nums2RightMin (j n) ? Integer.MAX_VALUE : nums2[j]; if ((m n) % 2 1) { return Math.max(nums1LeftMax, nums2LeftMax); } else { return (Math.max(nums1LeftMax, nums2LeftMax) Math.min(nums1RightMin, nums2RightMin)) / 2.0; } }第九部分总结与学习路径9.1 核心要点回顾核心思想利用有序性每次将搜索范围减半。适用条件有序 随机访问。时间复杂度$O(\log n)$空间复杂度$O(1)$。三种模板标准模板闭区间left right直接返回。左边界模板左闭右开left right返回第一个 ≥ target 的索引。右边界模板左闭右开left right返回最后一个 ≤ target 的索引。常见应用旋转数组、二维矩阵、峰值查找、平方根、二分答案。易错点死循环、边界溢出、索引越界。高级思维将优化问题转化为判定问题。9.2 学习路径建议初级阶段熟练掌握标准二分查找能够无误地写出代码并理解循环不变式。中级阶段掌握左边界和右边界模板能够解决lower_bound和upper_bound问题。开始接触旋转数组、峰值查找等变体。高级阶段掌握二分答案的思想能够独立解决“最大值最小化”和“最小值最大化”问题。学习在复杂数据结构如线段树、并查集中应用二分查找。升华阶段理解二分查找的本质是单调性决策能够将问题转化为判定问题并灵活运用。阅读 STL 源码学习工业级的实现细节。9.3 结语二分查找算法简洁而深刻。它告诉我们在面对有序的信息时智慧的选择可以让我们事半功倍。从最初的“猜数字”游戏到复杂算法中的决策基石二分查找始终是算法设计者手中的一把利器。掌握二分查找不仅仅是记住几段代码更是理解了一种思维范式在单调的世界里我们可以通过不断缩小范围以对数级的代价逼近真相。