java 二分查找
🌐 www.xservx.com · 程序员技术成长平台

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:

📊 与线性查找对比

算法 前提条件 时间复杂度 空间复杂度 适用场景
线性查找 无 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):

⚠️ 边界与陷阱

二分查找的“魔鬼在细节”:边界处理错误是线上事故的高频根源。以下四类典型陷阱需重点防范。

陷阱①:整型溢出

错误写法: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

💡 变种设计思想总结

⚖️ 与其他查找算法对比

在不同数据规模与访问模式下,选择最优查找算法是性能优化的关键环节。

算法 时间复杂度 空间复杂度 适用数据结构 是否需有序 适用场景
线性查找 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为负。

📝 面试加分项

🚀 工程优化策略

理论最优不等于实际最快。在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);

🔥 性能陷阱警示

🔧 实际应用场景

二分查找绝非仅用于“查数字”,其思想已深度融入各类系统设计。

① 时间序列数据查询

日志系统按时间戳排序,快速定位某时间段日志。例如:Elasticsearch的倒排索引分段存储,查询时用二分定位段。

② 二分查找树(BST)遍历

在TreeMap中查找key时,本质是在红黑树上执行“二分查找”:每次比较当前节点,决定向左/右子树深入。

③ 动态规划优化

如“最长递增子序列”(LIS)的O(n log n)解法:维护一个tail数组,用二分查找找到首个≥当前元素的位置并替换。

④ 系统资源分配

内存管理中,buddy系统用二分查找分配连续页框;网络调度中,按权重分配带宽时用前缀和+二分。

💡 真实案例:电商库存扣减

某平台在秒杀活动中,将库存按时间戳分段存储(每分钟一段),查询某时刻库存时:先用二分定位时间段,再在段内二分查找精确库存。相比全量扫描,QPS提升10倍以上。