在近乎有序数组中高效查找目标值的改进二分搜索算法-java教程-PHP中文网

在近乎有序数组中高效查找目标值的改进二分搜索算法

本文介绍一种针对“近乎有序数组”（即去零后严格升序、最多含 k 个连续零的非负整数数组）的 o(log n + k) 时间复杂度查找算法，通过动态扩展探查范围替代传统二分中的单一中点访问，避免重复扫描零值。

本文介绍一种针对“近乎有序数组”（即去零后严格升序、最多含 k 个连续零的非负整数数组）的 o(log n + k) 时间复杂度查找算法，通过动态扩展探查范围替代传统二分中的单一中点访问，避免重复扫描零值。

在标准二分搜索中，我们依赖数组的全局有序性来安全地舍弃一半搜索区间。但本题中，数组虽“几乎有序”，却因存在连续零段而破坏了局部单调性——直接取 a[mid] 可能为 0，无法判断目标值应落在左半还是右半。若简单跳转至最近非零元素（如原代码中 closestLeft/closestRight），可能引发边界错位、区间重叠或重复检查，导致最坏时间复杂度退化至 O(n)。

核心思路是：不预设“中点值必须非零”，而是以 mid 为中心，按曼哈顿距离递增顺序螺旋式向外探查非零元素。具体策略如下：

每次迭代计算 mid = (low + high) / 2；
从 mid 出发，依次检查 mid, mid−1, mid+1, mid−2, mid+2, …（即偏移量序列：0, −1, +1, −2, +2, …）；
一旦找到 a[m] ≠ 0，立即用该值参与比较；
若在整个 [low, high) 范围内未找到非零值，说明该子数组全为零 → 目标值（正整数）不可能存在，直接返回 -1；
关键优化：缩小区间时，利用已定位的非零位置 m 精确裁剪：
- 若 num
- 若 num > a[m]，则有效值必在 m 右侧，故新 low = max(m, mid) + 1（跳过 m 及左侧已探查部分）。

该设计保证：

每轮探查最多访问 O(k) 个零（因任意连续零段长度 ≤ k，且探查范围不会跨过未被覆盖的有效值）；
每个零至多被访问一次（因区间收缩排除了已探查区域）；
总时间复杂度为 O(log n + k)，优于朴素线性扫描的 O(n)，且当 k 为常数时等价于 O(log n)。

以下是完整可运行实现（注意：high 定义为开区间上界，符合 Java 数组习惯）：

public static int kAlmostSearch(int[] a, int num) {
    if (a == null || a.length == 0) return -1;

    int low = 0;
    int high = a.length; // [low, high) is the current search range

    while (low = low && m = high) {
                return -1;
            }
        }

        if (a[m] == num) {
            return m;
        } else if (num <p><strong>注意事项与验证要点</strong>：  </p>