二分查找Java

⚡ 二分查找Java核心原理与应用场景

二分查找(Binary Search)是一种在有序数据集中查找目标值的高效算法,其时间复杂度为O(log n),远优于线性查找的O(n)。在Java开发中,该算法广泛应用于排序数组检索、数据库索引模拟、算法题解题(如LeetCode高频题)、系统性能优化等场景。其核心思想是“分而治之”:每次将搜索区间折半,通过比较中间元素与目标值的大小关系,决定继续搜索左半区还是右半区,从而快速收敛至目标位置。

二分查找并非仅限于“查找等于目标值的下标”这一基础功能,其本质是对“有序性”的利用。只要问题满足“单调性”或“可二分性”,即可应用二分思想进行求解——这正是其在算法设计中占据核心地位的原因。在Java中,开发者不仅可手动实现标准二分查找,还可借助JDK内置的Arrays.binarySearch()与Collections.binarySearch()方法,实现高效检索,但需注意:这些方法要求输入数组必须是**已排序**的,否则结果不可靠。

值得注意的是,二分查找的**鲁棒性实现远比直觉复杂**:整数溢出问题(mid = (l + r) / 2在l+r接近int上限时会溢出)、边界条件处理(左闭右开 vs 左闭右闭)、循环终止条件选择(while (l <= r) vs while (l < r))、相等时的收敛策略(是否允许重复元素、返回最左/最右位置)等,均是实际开发中高频踩坑点。例如,JDK 1.8中Arrays.binarySearch()的实现即采用mid = l + ((r - l) >> 1)规避溢出,体现了工程级代码的严谨性。

从算法教学角度,二分查找是理解“递归”与“迭代”两种范式的经典范例;从工程实践角度,它是构建高效搜索服务的基石(如Elasticsearch的倒排索引检索虽更复杂,但底层仍蕴含二分思想);从面试维度,其变体题(如“旋转数组查找”、“第一个错误版本”、“吃香蕉的珂珂”)已成为大厂算法面试的“标配”,深刻考察候选人对边界条件的掌控力与逻辑严密性。

💡 核心前提:数据必须有序!若数据无序,强行二分将导致逻辑错误。常见误区是忽略“排序”前置步骤,应确保:1)插入数据时维护有序性;2)查找前先排序(O(n log n))。需权衡排序成本与多次查找收益:若仅查找1-2次,直接线性扫描更优;若高频查找,排序后二分更高效。

⚙️ 标准二分查找Java实现详解

以下提供三种主流实现方式:**基础迭代版**(最常用)、**递归版**(体现分治思想)、**JDK源码风格版**(工业级健壮性)。所有实现均基于**左闭右闭区间**[l, r],即初始调用为binarySearch(arr, target, 0, arr.length - 1)。

① 基础迭代实现(推荐日常使用)

该实现逻辑清晰、无额外调用栈开销,是生产环境首选:

public class BinarySearch {
    public static int search(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            // 防溢出:mid = left + (right - left) / 2
            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(log n),大输入时可能栈溢出,不推荐生产使用:

public class BinarySearch {
    public static int searchRecursive(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 searchRecursive(arr, target, mid + 1, right);
        } else {
            return searchRecursive(arr, target, left, mid - 1);
        }
    }
    // 对外暴露的便捷方法
    public static int searchRecursive(int[] arr, int target) {
        return searchRecursive(arr, target, 0, arr.length - 1);
    }
}

③ JDK源码风格版(规避整数溢出)

参考JDK 1.8Arrays.binarySearch(int[], int)实现,采用位运算优化性能:

public class BinarySearch {
    public static int searchJDKStyle(int[] a, int key) {
        int low = 0;
        int high = a.length - 1;
        while (low <= high) {
            int mid = (low + high) >>> 1; // 无符号右移,等价于除2
            int midVal = a[mid];
            if (midVal < key) {
                low = mid + 1;
            } else if (midVal > key) {
                high = mid - 1;
            } else {
                return mid;
            }
        }
        return -(low + 1); // 插入点负表示
    }
}

注:JDK返回“插入点”的负值(-(insertionPoint) - 1),插入点即“第一个大于target的索引”。例如数组[1,3,5]查4,插入点为2(5的位置),返回-(2+1) = -3,表示“若插入4,应放在索引2处”。此设计便于判断查找失败时的插入位置,是工程级设计的典范。

〔 边界条件与常见陷阱深度剖析 〕

二分查找的正确性高度依赖边界处理。以下总结高频错误点及规避方案:

① 整数溢出问题

当left和right均接近int最大值(2^31-1=2147483647)时,left + right可能超过2^31,导致负数溢出。例如:left=2147483646, right=2147483647,和为4294967293 > 2^31-1,溢出为负值。

✅ 正确写法(三种等效方案)

  • mid = left + (right - left) / 2(推荐,避免中间值溢出)
  • mid = (left + right) >>> 1(JDK方案,无符号右移1位)
  • mid = (left & right) + ((left ^ right) >> 1)(位运算优化,极少用)

② 循环终止条件选择

左闭右闭区间 [l, r]:终止条件为l > r,即while (l <= r);
左闭右开区间 [l, r):终止条件为l == r,即while (l < r)。二者逻辑不同,不可混用!

⚠️ 混用后果: 若用右开区间写法但初始right = arr.length - 1(应为arr.length),会导致漏查最后一个元素。

③ 更新边界策略

当arr[mid] != target时,需收缩搜索区间:

错误写法:left = mid或right = mid会导致死循环!例如left=0, right=1, mid=0,若arr[0] < target,left仍为0,循环无法终止。

④ 重复元素处理

标准二分查找返回**任意一个**匹配位置。若需返回**第一个/最后一个**匹配项,需修改收敛逻辑:

// 查找第一个等于target的下标
public static int findFirst(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] >= target) {
            if (arr[mid] == target) result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return result;
}

核心思想:即使找到目标值,仍继续向左收缩(right = mid - 1),确保找到最左位置。同理,查找最后一个匹配项需向右收缩。

〔 二分查找变体:超越基础查找 〕

二分思想的精髓在于“**在有序性中搜索**”,以下变体虽形式各异,但均遵循二分核心逻辑:

① 旋转排序数组查找(LeetCode #33)

问题:升序数组在未知点旋转后(如[4,5,6,7,0,1,2]),查找目标值。关键:**每次二分必有一半区间有序**!

核心洞察:旋转数组可视为两个有序段拼接。每次计算mid后,判断哪半段有序:

  • 若arr[l] ≤ arr[mid]:左半段[l, mid]有序;若target在[l, mid]内,则收缩右边界,否则收缩左边界
  • 否则右半段[mid, r]有序;若target在[mid, r]内,则收缩左边界,否则收缩右边界

例:数组[4,5,6,7,0,1,2],target=0:

  • 初始 l=0, r=6, mid=3 → arr[mid]=7;arr[l]=4 ≤7 → 左半段有序;0不在[4,7] → left=4
  • l=4, r=6, mid=5 → arr[mid]=1;arr[l]=0 ≤1 → 左半段有序;0在[0,1] → right=5
  • l=4, r=5, mid=4 → arr[mid]=0 → 返回4
public class Solution {
    public int 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;
            // 左半段有序 [left, mid]
            if (nums[left] <= nums[mid]) {
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } // 右半段有序 [mid, right]
            else {
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}
指标 值
时间复杂度 O(log n)
空间复杂度 O(1)
适用场景 旋转排序数组、循环有序数组

② 第一个错误版本(LeetCode #278)

问题:n个版本[1,2,...,n],从某版本起全错误。已知isBadVersion(version)接口,求第一个错误版本。本质:**查找第一个满足条件的位置**(类似“第一个≥target”)。

关键点

  • 当isBadVersion(mid)为true,第一个错误版本在[mid, n];为false,在[mid+1, n]
  • 循环条件:while (left < right)(最终left==right即结果)
  • 更新策略:right = mid(不能-1,因mid可能为答案)
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {
                right = mid; // 第一个错误版本 ≤ mid
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

③ 搜索插入位置(LeetCode #35)

问题:在有序数组中查找target,若存在返回索引;否则返回应插入位置(保持有序)。本质:**查找第一个≥target的位置**。

public class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length;
        // 左闭右开区间 [0, n)
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid; // 插入点 ≤ mid
            } else {
                left = mid + 1;
            }
        }
        return left; // left即第一个≥target的位置
    }
}

示例:数组[1,3,5,6],target=5 → 返回2;target=2 → 返回1(插入3前);target=7 → 返回4(末尾)。

④ 零钱兑换II中的二分思想(LeetCode #518)

虽非直接二分,但利用“**答案单调性**”:若能用k种硬币组成amount,必能组成≤k的任意amount(非严格,但满足二分前提)。通过二分答案,结合动态规划验证可行性,将问题转化为O(log n)次DP计算。

💡 启示:二分查找不局限于数组下标,可应用于**任何单调函数的反函数求解**。例如:给定函数f(x),求f(x)=target的x值;或求满足条件的最小/最大x。

〔 JDK源码剖析:Arrays.binarySearch深度解析 〕

JDK提供了数组与集合的二分查找方法,但需注意其**前提条件与返回语义**:

① Arrays.binarySearch签名与行为

方法 参数说明 返回值含义 前提条件
binarySearch(int[] a, int key) 数组a、目标值key 找到则返回索引;否则返回-(insertionPoint) - 1 数组a必须**已排序**(升序)
binarySearch(int[] a, int fromIndex, int toIndex, int key) 子数组[fromIndex, toIndex) 同上,但搜索范围限定 子数组范围有效,且子数组已排序

注:insertionPoint是“第一个大于key的元素索引”,即插入位置。例如数组[1,3,5]查4,插入点为2(5的位置),返回-(2+1) = -3。

② 源码关键片段(JDK 1.8)

public static int binarySearch(int[] a, int key) {
    return binarySearch0(a, 0, a.length, key);
}
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                             int key) {
    int low = fromIndex;
    int high = toIndex - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = a[mid];
        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1); // key not found.
}

关键设计:
• 使用无符号右移>>>避免溢出;
• 返回插入点负值,便于区分查找失败与成功;
• 未处理null数组,调用前需确保非空。

③ 使用陷阱与最佳实践

❌ 常见错误

  • 数组未排序:直接调用binarySearch → 结果不可预测
  • 误判返回值:查失败时返回负数,但非简单“-1”,需用Arrays.binarySearch(arr, key) < 0判断
  • 未处理重复元素:返回任意匹配位置,非第一个/最后一个

✅ 最佳实践

  1. 查找前显式排序:Arrays.sort(arr);
  2. 处理失败情况:int index = Arrays.binarySearch(arr, key); if (index < 0) { int pos = -index - 1; ... }
  3. 需找第一个匹配项:先查任意位置,再线性扫描左侧(因重复元素可能连续)

示例:查找并处理插入位置:

int[] arr = {1, 3, 5, 7};
int key = 4;
int index = Arrays.binarySearch(arr, key);
if (index >= 0) {
    System.out.println("Found at " + index);
} else {
    int pos = -index - 1;
    System.out.println("Insert at " + pos + ", value " + key + " will be between " +
                       (pos > 0 ? arr[pos-1] : "start") + " and " +
                       (pos < arr.length ? arr[pos] : "end"));
}

输出:Insert at 2, value 4 will be between 3 and 5

〔 时间与空间复杂度深度对比 〕

二分查找的复杂度常被简化为“O(log n)”,但具体场景需细化分析:

① 基础二分查找复杂度

场景 时间复杂度 空间复杂度 说明
迭代实现 O(log n) O(1) 仅需常量空间存储索引
递归实现 O(log n) O(log n) 调用栈深度为O(log n)
最坏情况 O(log n) 同上 目标不存在,需搜索至区间为空
平均情况 O(log n) 同上 假设目标均匀分布

② 与线性查找对比

⚡ 性能转折点:当n=2^20≈100万时,log₂n=20;线性查找平均需50万次比较,二分查找仅需20次。n越大,优势越显著。但n较小时(如n<10),线性查找因常数因子小反而更快。

实测数据(Java 17,Intel i7):

n 线性查找(ns) 二分查找(ns) 二分优势
10 25 30 劣势
100 250 55 4.5×
10,000 25,000 100 250×
1,000,000 2,500,000 160 15,625×

注:实际性能受CPU缓存、分支预测影响。二分查找访问模式更规律,缓存局部性更好,优势可能被放大。

③ 变体复杂度分析

变体 时间复杂度 关键变量
标准查找 O(log n) 比较次数≈log₂n
查找第一个匹配项 O(log n) 仍为二分,但收敛策略不同
旋转数组查找 O(log n) 每次判断有序段
二维矩阵查找(Z字形) O(m + n) 非二分,但常被混淆
二维矩阵二分查找 O(log(mn)) 将矩阵视为长度mn的一维数组

④ 空间复杂度优化

迭代版空间复杂度O(1),但若需存储中间状态(如递归转迭代的显式栈),空间可能升至O(log n)。实际中应优先选择迭代实现。

〔 实战场景:从LeetCode到生产代码 〕

以下场景展示二分查找在真实开发中的应用:

① LeetCode高频题解

题1:山脉数组的峰顶索引(LeetCode #852)

问题:给定山脉数组(先增后减),求峰值索引。解法:二分比较mid与mid+1,若arr[mid] < arr[mid+1],峰在右;否则在左(含mid)。

public class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

题2:在D天内送达包裹的能力(LeetCode #1011)

问题:求最小运载能力D,使包裹能在T天内运完。解法:**答案二分**!运载能力范围[最大单件重量, 总重量],对每个能力值用贪心验证所需天数。

public class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int left = Arrays.stream(weights).max().getAsInt();
        int right = Arrays.stream(weights).sum();
        while (left < right) {
            int capacity = left + (right - left) / 2;
            if (canShip(weights, days, capacity)) {
                right = capacity;
            } else {
                left = capacity + 1;
            }
        }
        return left;
    }
    private boolean canShip(int[] weights, int days, int capacity) {
        int day = 1, current = 0;
        for (int w : weights) {
            if (current + w > capacity) {
                day++;
                current = 0;
            }
            current += w;
        }
        return day <= days;
    }
}

② 生产环境应用案例

案例1:日志检索系统

场景:日志按时间戳排序存储,用户按时间范围查询。方案:用二分查找定位起始时间戳的插入点,再线性扫描至结束时间戳。比全表扫描快100倍+。

// 查找第一个≥startTime的日志索引
int startIdx = Arrays.binarySearch(timestamps, startTime);
if (startIdx < 0) startIdx = -startIdx - 1;
// 查找第一个>endTime的日志索引
int endIdx = Arrays.binarySearch(timestamps, endTime + 1);
if (endIdx < 0) endIdx = -endIdx - 1;
List<Log> result = logs.subList(startIdx, endIdx);

案例2:配置项热更新

场景:配置按生效时间戳排序,用户请求时需快速找到最新生效配置。方案:二分查找当前时间戳的插入点,返回前一个配置项。

int idx = Arrays.binarySearch(configTimestamps, currentTime);
if (idx < 0) idx = -idx - 2; // 插入点-1 = 最后一个≤currentTime的索引
if (idx >= 0) {
    return configs[idx];
} else {
    return defaultConfig;
}