二分查找的两种核心类型：精准查找与近似查找（Java实现与场景分析）

📅 2026-01-05 14:36:49阅读时间: 23分钟

二分查找的两种核心类型：精准查找与近似查找（Java实现与场景分析）

前言

二分查找（Binary Search）作为有序数组的高效查找算法，其时间复杂度为O(log n)，远优于线性查找的O(n)。根据查找需求的不同，二分查找可分为两大核心类型：精准查找与近似查找。精准查找是二分查找的原始形态，专注于判断目标值是否存在并返回其精确索引；近似查找则是精准查找的扩展，用于在目标值不存在时，找到与目标值最接近的元素，满足实际业务中的模糊匹配需求。本文将详细讲解这两种查找类型的原理、Java实现及适用场景。

一、 精准查找（Exact Binary Search）

1. 核心定义与原理

精准查找是二分查找的基础形态，其核心目标是在有序数组中精准匹配目标值：若目标值存在，返回其在数组中的索引；若目标值不存在，返回一个约定的无效标识（通常为-1，因数组索引非负，-1可明确表示“未找到”）。

其实现原理基于分治思想，通过不断折半缩小查找区间实现高效查找，核心步骤如下：

  1. 初始化查找区间的左边界left=0，右边界right=数组长度-1（闭区间[left, right]）；

  2. 计算安全中间索引mid = left + (right - left) / 2（避免left + right整数溢出）；

  3. 比较中间元素nums[mid]与目标值target：

    • 若nums[mid] == target：精准匹配成功，返回mid；

    • 若nums[mid] > target：目标值在左半区间，调整右边界right = mid - 1；

    • 若nums[mid] < target：目标值在右半区间，调整左边界left = mid + 1；

  4. 重复步骤2-3，直到找到目标值或查找区间失效（left > right），区间失效时返回-1表示未找到。

2. Java代码实现（迭代+递归）

（1）迭代实现（推荐，无栈溢出风险，空间复杂度O(1)）

Java 复制代码 
public class ExactBinarySearch {
    /**
     * 迭代式精准二分查找
     * @param nums 升序有序数组
     * @param target 待精准匹配的目标值
     * @return 目标值索引（未找到返回-1）
     */
    public static int exactBinarySearchIterative(int[] nums, int target) {
        // 边界校验：数组为空或长度为0，直接返回-1
        if (nums == null || nums.length == 0) {
            return -1;
        }

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

        // 区间有效时继续查找
        while (left <= right) {
            // 安全计算中间索引，避免整数溢出
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid; // 精准匹配，返回索引
            } else if (nums[mid] > target) {
                right = mid - 1; // 目标在左半区间，调整右边界
            } else {
                left = mid + 1; // 目标在右半区间，调整左边界
            }
        }

        // 区间失效，未找到目标值，返回-1
        return -1;
    }

    // 测试方法
    public static void main(String[] args) {
        int[] sortedNums = {1, 3, 5, 7, 9, 11, 13, 15};
        int targetExist = 7; // 存在的目标值
        int targetNotExist = 8; // 不存在的目标值

        int index1 = exactBinarySearchIterative(sortedNums, targetExist);
        int index2 = exactBinarySearchIterative(sortedNums, targetNotExist);

        System.out.println("目标值 " + targetExist + " 的精准索引：" + index1); // 输出3
        System.out.println("目标值 " + targetNotExist + " 的精准索引：" + index2); // 输出-1
    }
}

（2）递归实现（代码简洁，存在栈溢出风险，空间复杂度O(log n)）

Java 复制代码 
public class ExactBinarySearchRecursive {
    /**
     * 递归式精准二分查找
     * @param nums 升序有序数组
     * @param target 待精准匹配的目标值
     * @param left 查找区间左边界
     * @param right 查找区间右边界
     * @return 目标值索引（未找到返回-1）
     */
    public static int exactBinarySearchRecursive(int[] nums, int target, int left, int right) {
        // 递归终止条件：区间失效，返回-1
        if (left > right) {
            return -1;
        }

        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            return mid; // 精准匹配，返回索引
        } else if (nums[mid] > target) {
            // 递归查找左半区间
            return exactBinarySearchRecursive(nums, target, left, mid - 1);
        } else {
            // 递归查找右半区间
            return exactBinarySearchRecursive(nums, target, mid + 1, right);
        }
    }

    // 测试方法
    public static void main(String[] args) {
        int[] sortedNums = {1, 3, 5, 7, 9, 11, 13, 15};
        int targetExist = 13;
        int targetNotExist = 6;

        // 初始调用传入完整区间边界
        int index1 = exactBinarySearchRecursive(sortedNums, targetExist, 0, sortedNums.length - 1);
        int index2 = exactBinarySearchRecursive(sortedNums, targetNotExist, 0, sortedNums.length - 1);

        System.out.println("目标值 " + targetExist + " 的精准索引：" + index1); // 输出6
        System.out.println("目标值 " + targetNotExist + " 的精准索引：" + index2); // 输出-1
    }
}

3. 适用场景

精准查找适用于需要明确判断目标值是否存在，且需获取其精确位置的场景，常见示例：

  1. 数据字典查询：如根据用户ID（唯一有序）查询用户在数组中的索引，进而获取用户完整信息；

  2. 有序数组的存在性校验：如判断某个数字是否在有序的成绩数组中，快速筛选合格/不合格人员；

  3. 数据库索引查询：底层基于二分查找的变种（B+树），实现主键的精准查询，快速定位数据行；

  4. 配置项查找：在有序的配置参数数组中，精准匹配目标配置项的key，获取对应value。

二、 近似查找（Approximate Binary Search）

1. 核心定义与原理

近似查找是精准查找的扩展形态，其核心目标是：当目标值不存在于有序数组中时，找到与目标值最接近的元素（最小差值对应的元素）；若目标值存在，则直接返回其索引（自身即为最接近的元素）。

其实现原理基于精准查找的框架，核心扩展点是在查找过程中持续记录并更新“最接近元素的索引”，具体步骤如下：

  1. 初始化左边界left=0、右边界right=数组长度-1，同时初始化nearestIndex（保存最接近元素索引，初始值可设为0）；

  2. 计算中间索引mid = left + (right - left) / 2；

  3. 比较nums[mid]与target的差值绝对值，若当前nums[mid]比nums[nearestIndex]更接近target，则更新nearestIndex = mid；

  4. 按照精准查找的逻辑调整查找边界（寻找精准匹配值）：

    • 若nums[mid] == target：直接返回mid（精准匹配，无需继续查找）；

    • 若nums[mid] > target：调整right = mid - 1；

    • 若nums[mid] < target：调整left = mid + 1；

  5. 重复步骤2-4，直到查找区间失效（left > right）；

  6. 区间失效后，返回记录的nearestIndex（即最接近目标值的元素索引）。

2. Java代码实现（迭代优先，避免栈溢出）

Java 复制代码 
public class ApproximateBinarySearch {
    /**
     * 迭代式近似二分查找（查找最接近目标值的元素索引）
     * @param nums 升序有序数组
     * @param target 待查找的目标值
     * @return 最接近目标值的元素索引（数组为空返回-1）
     */
    public static int approximateBinarySearch(int[] nums, int target) {
        // 边界校验：数组为空或长度为0，返回-1
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int left = 0;
        int right = nums.length - 1;
        int nearestIndex = 0; // 初始化最接近元素索引

        while (left <= right) {
            int mid = left + (right - left) / 2;

            // 核心：更新最接近元素的索引
            // 比较当前mid对应元素与已有最接近元素的差值绝对值
            if (Math.abs(nums[mid] - target) < Math.abs(nums[nearestIndex] - target)) {
                nearestIndex = mid;
            }
            // 特殊情况：若两个元素与目标值差值相等，可选择保留左侧元素（或右侧，按需调整）
            else if (Math.abs(nums[mid] - target) == Math.abs(nums[nearestIndex] - target)) {
                // 此处选择保留索引较小的元素（即左侧元素），可根据业务需求修改
                nearestIndex = Math.min(nearestIndex, mid);
            }

            // 精准匹配时，直接返回mid
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        // 区间失效，返回最接近元素的索引
        return nearestIndex;
    }

    // 测试方法
    public static void main(String[] args) {
        int[] sortedNums = {1, 3, 5, 7, 9, 11, 13, 15};
        int targetNotExist = 8; // 不存在的目标值，最接近7（索引3）和9（索引4）
        int targetExist = 7; // 存在的目标值
        int targetEdge = 0; // 小于数组所有元素，最接近1（索引0）
        int targetEdge2 = 16; // 大于数组所有元素，最接近15（索引7）

        int index1 = approximateBinarySearch(sortedNums, targetNotExist);
        int index2 = approximateBinarySearch(sortedNums, targetExist);
        int index3 = approximateBinarySearch(sortedNums, targetEdge);
        int index4 = approximateBinarySearch(sortedNums, targetEdge2);

        System.out.println("与 " + targetNotExist + " 最接近的元素索引：" + index1 + "，对应元素：" + sortedNums[index1]); // 输出3，对应7
        System.out.println("与 " + targetExist + " 最接近的元素索引：" + index2 + "，对应元素：" + sortedNums[index2]); // 输出3，对应7
        System.out.println("与 " + targetEdge + " 最接近的元素索引：" + index3 + "，对应元素：" + sortedNums[index3]); // 输出0，对应1
        System.out.println("与 " + targetEdge2 + " 最接近的元素索引：" + index4 + "，对应元素：" + sortedNums[index4]); // 输出7，对应15
    }
}

3. 适用场景

近似查找适用于无需精准匹配，仅需获取与目标值最接近的元素的场景，常见示例：

  1. 价格匹配系统：如电商平台中，用户输入一个心理价格，快速找到最接近该价格的商品（无需价格完全一致）；

  2. 温度/湿度等传感器数据：如在有序的历史传感器数据中，查找与当前监测值最接近的历史数据，用于趋势分析；

  3. 模糊查询补全：如通讯录按拼音首字母有序排列，用户输入错误拼音时，返回最接近的联系人；

  4. 阈值匹配：如在有序的评分区间数组中，用户分数未精准匹配任何阈值时，找到最接近的阈值，确定对应的等级（如考试分数61分，最接近60分及格线）；

  5. 地理坐标查找：在有序的经纬度数组中，查找与目标坐标最接近的地点，实现附近地点推荐的基础功能。

三、 精准查找与近似查找核心对比

对比维度 精准查找 近似查找
核心目标 精准匹配目标值，返回索引 找到最接近目标值的元素索引
未找到目标值时 返回约定标识（如-1） 返回最接近元素的有效索引
核心扩展 无额外逻辑 记录并更新最接近元素索引
时间复杂度 O(log n) O(log n)
空间复杂度（迭代） O(1) O(1)
空间复杂度（递归） O(log n) O(log n)
核心特性 存在性判断+精准定位 模糊匹配+邻近值获取

四、 总结

  1. 二分查找的两大核心类型（精准查找、近似查找）均基于分治思想，时间复杂度均为O(log n)，仅在功能目标和逻辑细节上存在差异；

  2. 精准查找是基础，适用于需要明确存在性判断和精准索引的场景，未找到目标值时返回-1，迭代实现更安全高效；

  3. 近似查找是精准查找的扩展，适用于模糊匹配场景，通过记录最接近元素索引，在目标值不存在时返回有效结果；

  4. 实际开发中，需根据业务需求选择：若需精准匹配（如ID查询），使用精准查找；若需邻近值匹配（如价格推荐），使用近似查找。

返回文章列表