Java 中实现二分查找算法的完整教程-java教程-PHP中文网

本文详细讲解如何在 java 中正确实现二分查找算法：包括核心逻辑、迭代与递归两种写法、边界处理要点、时间复杂度分析，并提供可直接运行的完整示例代码。

本文详细讲解如何在 java 中正确实现二分查找算法：包括核心逻辑、迭代与递归两种写法、边界处理要点、时间复杂度分析，并提供可直接运行的完整示例代码。

二分查找（Binary Search）是一种高效、经典的搜索算法，仅适用于已排序的数组。其核心思想是通过持续缩小搜索范围——每次比较中间元素与目标值，根据大小关系决定舍弃左半区或右半区，从而将时间复杂度稳定控制在 O(log n)，远优于线性查找的 O(n)。

✅ 算法逻辑详解

初始化左右边界：left = 0，right = arr.length - 1；
循环条件为 left
计算中点索引：推荐使用 mid = left + (right - left) / 2，避免 left + right 可能导致的整型溢出（尤其在大数组中）；
比较 arr[mid] 与目标值 x：
- 相等 → 返回 mid；
- arr[mid]
- arr[mid] > x → 目标在左半区 → 更新 right = mid - 1；
循环结束仍未找到 → 返回 -1。

? 迭代实现（推荐，空间效率高）

以下为健壮、生产就绪的迭代版本（含注释与关键优化）：

public class BinarySearch {
    /**
     * 在升序整型数组中查找目标值，返回首次出现的索引，未找到返回-1
     * @param arr 升序排列的非空数组
     * @param target 待查找的目标值
     * @return 目标值索引，或-1
     */
    public static int search(int[] arr, int target) {
        if (arr == null || arr.length == 0) return -1;

        int left = 0;
        int right = arr.length - 1;

        while (left <h3>? 递归实现（便于理解分治思想）</h3><p>若需递归版本，可封装为私有辅助方法，避免重复创建栈帧开销：</p><div class="aritcle_card flexRow artxards">
											<div class="artcardd flexRow">
												<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill10962" title="Java 接口排错助手"><img
														src="https://img.php.cn/upload/skill/001/246/273/6adaf20dbae7c507.jpg" alt="Java 接口排错助手" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
												<div class="aritcle_card_info flexColumn">
													<a rel="nofollow" href="/xiazai/skill10962" title="Java 接口排错助手" class="overflowclass">Java 接口排错助手</a>
													<p class="overflowclass">在调试 Java 后端 API 故障时使用此技能，尤其适用于以下任务：分析日志、跨 Controller、Service 和 Mapper 层追踪请求、定位异常根因、检查 SQL 执行或参数流转，以及生成简洁的诊断结论与修复方案。</p>
												</div>
												<a rel="nofollow" href="/xiazai/skill10962" title="Java 接口排错助手" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
												</a>
											</div>
										</div><pre class="brush:php;toolbar:false;">public static int searchRecursive(int[] arr, int target) {
    if (arr == null || arr.length == 0) return -1;
    return binarySearchHelper(arr, target, 0, arr.length - 1);
}

private static int binarySearchHelper(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] <h3>⚠️ 关键注意事项</h3>

前提条件：数组必须严格升序（或降序，此时需调整比较逻辑）；若无序，务必先调用 Arrays.sort()（但会带来 O(n log n) 开销，通常不推荐）；
数据类型扩展：泛型版需实现 Comparable 或传入 Comparator，例如 Collections.binarySearch()；
重复元素处理：上述实现返回任意一个匹配索引；如需最左/最右位置，需改用「查找边界」变体（如 lowerBound/upperBound）；
空数组与 null 安全：生产代码中务必校验输入，避免 NullPointerException 或 ArrayIndexOutOfBoundsException；
浮点数慎用：因精度问题，不建议对 double/float 数组直接二分，应转为整型坐标或使用误差容限比较。