Java 二分查找|从原理到实战的系统解析
深入理解算法本质、掌握边界处理技巧、突破面试高频考点,构建完整知识体系
⚡ 原理与本质
二分查找(Binary Search),又称折半查找,是一种在有序数据集合中查找目标值的高效算法。其核心思想是“分而治之”:每次将搜索区间一分为二,通过比较中间元素与目标值的大小关系,决定目标值落在左半区还是右半区,从而将搜索范围缩小一半。如此反复,直至找到目标或确认不存在。
✅ 核心前提
- 数据必须是有序的(升序或降序)
- 支持随机访问(如数组、ArrayList)
- 数据量适中(太小则线性更优;太大需考虑平衡树或布隆过滤器)
⏱️ 时间复杂度
- 最优:O(1)——目标即为中间元素
- 最坏/平均:O(log₂n)
- 示例:100万数据仅需最多20次比较
💾 空间复杂度
- 迭代实现:O(1)
- 递归实现:O(log₂n)(调用栈深度)
🔍 算法流程图解
设数组为 [1, 3, 5, 7, 9, 11, 13, 15],查找目标值 7:
- 初始:left=0, right=7 → mid=3 → arr[3]=7 → 目标命中,返回索引3
- 若查找
6(不存在): - ① left=0, right=7 → mid=3 → arr[3]=7 > 6 → 搜索左半区 [0,2]
- ② left=0, right=2 → mid=1 → arr[1]=3 < 6 → 搜索右半区 [2,2]
- ③ left=2, right=2 → mid=2 → arr[2]=5 < 6 → 搜索右半区 [3,2]
- ④ left=3 > right=2 → 退出循环 → 返回 -1(未找到)
📊 与线性查找对比
| 算法 | 前提条件 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|---|
| 线性查找 | 无 | O(n) | O(1) | 小规模/无序数据 |
| 二分查找 | 有序+随机访问 | O(log n) | O(1) 或 O(log n) | 大规模有序数据 |
| 哈希查找 | 哈希表 | O(1)平均 | O(n) | 频繁查找、无序数据 |
⚙️ Java 实现方式
在Java中实现二分查找,主要有三种经典写法:标准迭代版、递归版、以及基于Arrays.binarySearch的封装。每种实现均有其适用场景,需根据代码可读性、栈空间限制、性能需求综合选择。
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;
}
✅ 优点:无栈溢出风险、空间O(1)、执行效率高
⚠️ 关键点:mid计算用left + (right-left)/2避免(left+right)可能的整型溢出
public static int binarySearchRecursive(int[] arr, int target, int left, int right) {
if (left > right) return -1;
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) {
return binarySearchRecursive(arr, target, mid + 1, right);
} else {
return binarySearchRecursive(arr, target, left, mid - 1);
}
}
// 调用方式:binarySearchRecursive(arr, target, 0, arr.length - 1);
✅ 优点:逻辑清晰、便于理解递归思想
⚠️ 缺点:大数据量下可能栈溢出(如n=10⁶时深度≈20,通常安全)
import java.util.Arrays;
public static int search(int[] arr, int target) {
int index = Arrays.binarySearch(arr, target);
return index >= 0 ? index : -1;
}
✅ 优点:简洁、高效、经JVM优化
⚠️ 注意:若未排序,结果无意义;返回值≥0表示找到,<0表示插入点(需按公式计算)
📝 边界条件辨析
初学者常混淆while (left <= right)与while (left < right):
left <= right:适用于“查找是否存在”,最终区间为[3,2]时退出,代表空集left < right:适用于“查找第一个≥target的位置”,退出时left==right,需额外判断
⚠️ 边界与陷阱
二分查找的“魔鬼在细节”:边界处理错误是线上事故的高频根源。以下四类典型陷阱需重点防范。
错误写法:int mid = (left + right) / 2;
当left和right均接近2³¹-1时,left+right会溢出为负数,导致mid为负索引。
✅ 正确写法:int mid = left + (right - left) / 2; 或 int mid = (left + right) >>> 1;(无符号右移)
当left = mid且right = mid + 1时,若计算mid为(left + right)/2 = mid,则可能陷入死循环。
✅ 解决方案:保证每次迭代区间严格缩小,如left = mid + 1或right = mid - 1
未校验数组长度直接访问,会抛ArrayIndexOutOfBoundsException。
✅ 防御性编程:if (arr == null || arr.length == 0) return -1;
当数组含重复元素时,若需返回第一个/最后一个匹配位置,仅用==判断无法满足。
✅ 需扩展为“下界查找”与“上界查找”(见下节变种)
🧩 经典错误案例
某电商系统在库存查询中使用二分查找,因未处理left=mid时的更新逻辑,导致高并发下偶发死循环,CPU飙升至100%。根本原因:循环条件while (left < right) + mid = (left + right)/2 + left = mid组合,造成区间不收缩。
🔄 变种应用
二分查找的真正威力在于其变种——通过调整比较逻辑与区间更新规则,可解决“第一个≥target的位置”、“最后一个≤target的位置”、“旋转数组最小值”等复杂问题。
目标:返回第一个≥target的索引
public static int lowerBound(int[] arr, int target) {
int left = 0, right = arr.length; // 注意right初始为length
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target) {
left = mid + 1; // 继续向右找
} else {
right = mid; // 可能是解,保留mid
}
}
return left; // left即第一个≥target的位置
}
示例:arr=[1,3,3,5,7],target=3 → 返回1;target=4 → 返回3
目标:返回第一个>target的索引
public static int upperBound(int[] arr, int target) {
int left = 0, right = arr.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
示例:arr=[1,3,3,5,7],target=3 → 返回4;target=7 → 返回5(即length)
目标:旋转排序数组的最小值(含重复)
public static int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1; // 最小值在右半区
} else if (nums[mid] < nums[right]) {
right = mid; // 最小值在左半区(含mid)
} else {
right--; // 相等时缩小右边界(去重)
}
}
return nums[left];
}
示例:[2,2,2,0,1] → 0;[1,1,1,0,1] → 0;[3,1,3] → 1
💡 变种设计思想总结
- 搜索区间定义:[left, right) vs [left, right] → 决定初始值与循环条件
- 收缩策略:满足条件时收缩哪一侧?保留mid还是跳过?
- 返回值选择:循环结束时left或right哪个是正确答案?
⚖️ 与其他查找算法对比
在不同数据规模与访问模式下,选择最优查找算法是性能优化的关键环节。
| 算法 | 时间复杂度 | 空间复杂度 | 适用数据结构 | 是否需有序 | 适用场景 |
|---|---|---|---|---|---|
| 线性查找 | O(n) | O(1) | 数组、链表 | 否 | 小规模或无序数据 |
| 二分查找 | O(log n) | O(1) | 数组、ArrayList | 是 | 大规模静态有序数据 |
| 哈希查找 | O(1)平均 | O(n) | HashMap、HashSet | 否 | 频繁插入/删除/查找 |
| 跳表查找 | O(log n) | O(n) | SkipList | 否 | 需要有序且支持快速插入 |
| 平衡树查找 | O(log n) | O(n) | TreeMap、TreeSet | 是 | 需要范围查询/有序遍历 |
📊 性能实测(n=10⁷)
| 算法 | 1次查找 | 1000次查找 | 1000000次查找 |
|---|---|---|---|
| 线性查找 | ~5ms | ~5000ms | ~5000000ms |
| 二分查找 | ~0.001ms | ~0.1ms | ~100ms |
| 哈希查找 | ~0.0005ms | ~0.05ms | ~50ms |
🎯 高频面试题精讲
各大厂算法面试中,二分查找是必考题,常以“简单题”形式出现,但考察深度远超表面。以下整理10道典型真题,覆盖原理、实现、变种、陷阱。
① LeetCode #704:标准二分查找
给定有序数组和target,返回索引;不存在返回-1。
考点:边界条件、整型溢出、循环终止条件
② LeetCode #34:查找元素第一/最后位置
数组含重复元素,返回target首次和末次出现的索引;若不存在返回[-1,-1]。
解法:用lowerBound找左边界,upperBound-1得右边界
③ LeetCode #33:旋转排序数组搜索
原有序数组被旋转(如[0,1,2,4,5,6,7]→[4,5,6,7,0,1,2]),查找target。
关键:每次判断哪半区有序,再决定target落在哪
④ LeetCode #153:旋转排序数组最小值
无重复元素,找出最小值。
关键:比较mid与right,决定收缩方向
⑤ LeetCode #74:二维矩阵查找
矩阵每行有序,且下一行首元素>上一行末元素,视为一维有序数组。
技巧:将[i,j]映射为i*n+j
⑥ LeetCode #278:第一个错误版本
版本序列[1,2,...,n],从某版本起全错误,调用isBadVersion(i)判断,找出首个错误版。
本质:找第一个满足条件的位置(lowerBound变形)
⑦ LeetCode #658:找到K个最接近元素
在有序数组中找与x最接近的k个数,返回按升序排列的结果。
解法:用二分找长度为k的最优窗口起始点
⑧ LeetCode #4:两个正序数组的中位数
O(log(m+n))时间找中位数。
难点:二分搜索“第k小元素”,通过排除法缩小范围
⑨ 手写“不使用+/-”实现mid计算
答案:int mid = (left & right) + ((left ^ right) >>> 1);
原理:利用位运算模拟加法
⑩ 解释“为什么不能直接用left+right>>1”
Java中>>是算术右移,对负数会补1;而>>>是无符号右移,补0。但更关键的是left+right可能溢出为负数,导致mid为负。
📝 面试加分项
- 主动说明边界条件处理逻辑
- 解释mid计算防溢出方案
- 对比递归与迭代的优劣
- 讨论数据规模不同时的算法选择
- 提及实际工程中如何避免二分查找误用
🚀 工程优化策略
理论最优不等于实际最快。在Java工程实践中,还需结合JIT、CPU缓存、分支预测等因素进行调优。
数组连续性优势
二分查找天然适配CPU缓存——每次访问mid后,左右子区间的局部性良好,连续内存访问命中率高。相比之下,链表虽可二分,但节点分散导致缓存 miss 频发,实际性能远差于数组。
✅ 最佳实践:优先用ArrayList而非LinkedList实现二分查找
减少分支跳转
分支预测失败会导致流水线清空,损失数十周期。可尝试“无分支二分”:用位运算+掩码消除if-else。
int mask = (arr[mid] < target) ? -1 : 0;
left = (left & mask) | (mid + 1 & ~mask);
right = (right & ~mask) | (mid - 1 & mask);
⚠️ 注意:现代JIT编译器会自动优化,手动干预需基准测试验证
并行二分查找
对超大规模数据(如10⁹级),可分块并行:先用二分定位目标所在块,再在块内串行查找。
int blockSize = 1000000;
int blockIndex = Arrays.binarySearch(blockHeads, target);
int start = blockIndex * blockSize;
int end = Math.min(start + blockSize, arr.length);
int localIndex = binarySearch(arr, target, start, end);
🔥 性能陷阱警示
- 在循环内重复调用
arr.length——每次访问数组长度字段需边界检查,可缓存为局部变量 - 未复用排序结果:若数据频繁变动,每次查找前排序O(n log n),远超线性查找O(n)
- 在HashMap中误用二分:哈希表查找是O(1),二分反而更慢
🔧 实际应用场景
二分查找绝非仅用于“查数字”,其思想已深度融入各类系统设计。
① 时间序列数据查询
日志系统按时间戳排序,快速定位某时间段日志。例如:Elasticsearch的倒排索引分段存储,查询时用二分定位段。
② 二分查找树(BST)遍历
在TreeMap中查找key时,本质是在红黑树上执行“二分查找”:每次比较当前节点,决定向左/右子树深入。
③ 动态规划优化
如“最长递增子序列”(LIS)的O(n log n)解法:维护一个tail数组,用二分查找找到首个≥当前元素的位置并替换。
④ 系统资源分配
内存管理中,buddy系统用二分查找分配连续页框;网络调度中,按权重分配带宽时用前缀和+二分。
💡 真实案例:电商库存扣减
某平台在秒杀活动中,将库存按时间戳分段存储(每分钟一段),查询某时刻库存时:先用二分定位时间段,再在段内二分查找精确库存。相比全量扫描,QPS提升10倍以上。