每日算法 — 使用java实现指数搜索：有序数组边界自适应查找与二分搜索优化

算法概述

指数搜索（Exponential Search），又称翻倍搜索（Doubling Search）或 galloping search，是一种用于在有序数组中查找元素的高效算法。与二分搜索要求预先知道数组边界不同，指数搜索首先通过指数级跳跃快速定位目标元素可能存在的范围，然后在该范围内执行二分搜索。当目标元素靠近数组起始位置时，指数搜索的时间复杂度优于标准二分搜索，可达到O(log i)，其中i是目标元素的索引位置。

核心思想

指数搜索分为两个阶段：

阶段一：范围定位
从索引1开始，以指数级步长（1, 2, 4, 8, 16…）向右跳跃，直到找到第一个大于或等于目标值的边界。设跳跃终点为bound，则目标值（如果存在）必定位于索引bound/2和bound之间。

阶段二：二分搜索
在已确定的子范围[bound/2, min(bound, n-1)]内执行标准二分搜索。

这种策略特别适合以下场景：
– 数组长度未知或无限（如数据流）
– 目标元素大概率出现在数组前半部分
– 需要查找元素的插入位置

Java实现

import java.util.Arrays;

/**
 * 指数搜索（Exponential Search）算法实现
 * 适用于有序数组中查找元素，尤其在目标靠近开头时效率更高
 */
public class ExponentialSearch {

    /**
     * 标准二分搜索（辅助方法）
     * 在数组arr的[left, right]范围内查找target
     * @return target的索引，若不存在返回-1
     */
    public static int binarySearch(int[] arr, int left, int right, int target) {
        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(log i)，i为目标元素索引
     * @param arr 已排序数组
     * @param target 目标值
     * @return target的索引，若不存在返回-1
     */
    public static int exponentialSearch(int[] arr, int target) {
        int n = arr.length;

        // 边界检查
        if (n == 0) return -1;

        // 首先检查第一个元素
        if (arr[0] == target) {
            return 0;
        }

        // 阶段一：指数级跳跃定位范围
        // 从索引1开始，不断翻倍直到超出范围或找到边界
        int bound = 1;
        while (bound < n && arr[bound] <= target) {
            bound *= 2;
        }

        // 阶段二：在确定的范围内执行二分搜索
        // 左边界为bound/2（上一次的位置），右边界为min(bound, n-1)
        int left = bound / 2;
        int right = Math.min(bound, n - 1);

        return binarySearch(arr, left, right, target);
    }

    /**
     * 变体：查找目标值的插入位置（lower bound）
     * 返回第一个大于等于target的元素的索引
     */
    public static int exponentialLowerBound(int[] arr, int target) {
        int n = arr.length;

        if (n == 0) return 0;
        if (arr[0] >= target) return 0;

        int bound = 1;
        while (bound < n && arr[bound] < target) {
            bound *= 2;
        }

        int left = bound / 2;
        int right = Math.min(bound, n - 1);

        // 二分查找第一个>=target的位置
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }

    /**
     * 扩展：在无限/未知长度有序数组中查找
     * 模拟无限数组：通过指数搜索确定有效范围
     */
    public static int exponentialSearchUnbounded(int[] arr, int target) {
        int bound = 1;

        // 指数跳跃，处理可能的数组越界
        while (true) {
            try {
                if (arr[bound] >= target) {
                    break;
                }
                bound *= 2;
            } catch (ArrayIndexOutOfBoundsException e) {
                // 超出数组范围，目标在上一范围到数组末尾之间
                break;
            }
        }

        // 确定实际右边界
        int right = bound;
        try {
            while (right < arr.length && arr[right] < target) {
                right++;
            }
        } catch (ArrayIndexOutOfBoundsException e) {
            right = arr.length - 1;
        }

        return binarySearch(arr, bound / 2, Math.min(right, arr.length - 1), target);
    }

    /**
     * 性能对比测试
     */
    public static void performanceComparison() {
        int size = 1_000_000;
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = i * 2;  // 偶数序列
        }

        // 测试目标在数组前10%位置
        int target = arr[size / 10];
        int iterations = 10000;

        // 预热
        for (int i = 0; i < 100; i++) {
            exponentialSearch(arr, target);
            binarySearch(arr, 0, size - 1, target);
        }

        // 测试指数搜索
        long start = System.nanoTime();
        for (int i = 0; i < iterations; i++) {
            exponentialSearch(arr, target);
        }
        long expTime = System.nanoTime() - start;

        // 测试二分搜索
        start = System.nanoTime();
        for (int i = 0; i < iterations; i++) {
            binarySearch(arr, 0, size - 1, target);
        }
        long binTime = System.nanoTime() - start;

        System.out.printf("数组大小: %d, 目标位置: %d%n", size, size / 10);
        System.out.printf("指数搜索耗时: %.3f ms%n", expTime / 1_000_000.0);
        System.out.printf("二分搜索耗时: %.3f ms%n", binTime / 1_000_000.0);
        System.out.printf("加速比: %.2fx%n", (double) binTime / expTime);
    }

    public static void main(String[] args) {
        // 测试用例1：基本查找
        int[] arr = {2, 3, 4, 10, 40, 55, 68, 79, 85, 90, 100, 120};
        int target = 85;

        System.out.println("数组: " + Arrays.toString(arr));
        System.out.println("查找目标: " + target);

        int result = exponentialSearch(arr, target);
        System.out.println("指数搜索结果: 索引=" + result + ", 值=" + (result >= 0 ? arr[result] : "未找到"));

        // 测试用例2：查找不存在的元素
        target = 70;
        result = exponentialSearch(arr, target);
        System.out.println("查找 " + target + ": 索引=" + result);

        // 测试用例3：查找插入位置
        int insertPos = exponentialLowerBound(arr, 70);
        System.out.println("70的插入位置: " + insertPos + " (应插入在" + arr[insertPos] + "之前)");

        // 测试用例4：边界情况
        System.out.println("\n边界测试:");
        System.out.println("查找最小值2: 索引=" + exponentialSearch(arr, 2));
        System.out.println("查找最大值120: 索引=" + exponentialSearch(arr, 120));
        System.out.println("查找超出范围的值200: 索引=" + exponentialSearch(arr, 200));

        // 性能对比
        System.out.println("\n性能对比:");
        performanceComparison();
    }
}

算法对比分析

当目标元素位于索引i处时，指数搜索最多进行O(log i)次比较，而二分搜索始终需要O(log n)次。对于i远小于n的情况（如i=10, n=1,000,000），指数搜索可节省约50%的比较次数。

实际应用

指数搜索在以下场景中具有显著优势：

1. 前端分页加载：在按时间排序的数据流中查找某条记录，新记录大概率出现在前面。
2. 数据库索引：B+树叶子节点的前缀查找优化。
3. 版本控制系统：Git等工具中按时间排序的提交历史中查找特定提交。
4. 日志分析：按时间排序的日志文件中查找特定时间点的记录。
5. Auto-complete系统：在按频率排序的候选词列表中查找前缀匹配项。

指数搜索的优雅之处在于它自适应地调整搜索范围，无需预先知道数组的全局结构，是二分搜索在特定场景下的高效替代方案。