java - 给定以下约束，我如何找到索引？

Question

给定一个由 n 个整数组成的数组 A[0…n−1]，使得 ∀i,0≤i≤n，我们有 |A[i]−A[i+1]|≤1，如果 A[0 ]=x，A[n−1]=y，我们有 x<y。找到索引 j 使得 A[j]=z，对于给定的 z 值，x≤ z ≤y

我不明白这个问题。我已经坚持了4天。知道如何用二分搜索、指数搜索或递归插值搜索来处理它吗？我们给定一个元素 z 找到索引 j 使得 a [j] = z (aj) 我是对的吗？

Answer 1

这个：

| A[i]−A[i+1] | ≤ 1

意味着您的数组中的每个元素至多有一个不同的（-ve 或 +ve）。然后可以得出，可以包含当前z的最近索引是空格。|A[cur] - z|

所以，你要做的就是从 开始j=0，并为每一步弄清楚。跳过那么多空格，然后再次检查。最终你会找到 z 或到达终点。

public static int findZ(int[] a, int z){
    int j = 0;
    while(j < a.length){
        if(a[j] == z)
            return j
        j += Math.abs(a[j] - z);        
    }
    return -1;
}

这不是二进制或指数搜索，也不是递归的，但它很简单并且可以完成工作。它用作单边插值搜索。两种方法见下文。你可以把它变成一个递归函数，但这应该很简单，我会把它留给你。

它在 O(n) 中运行，在这种情况下，您的最坏情况性能将类似于{0,0,0,0,1}，它只能跳一步，然后变成直线搜索。

最好的情况将被排序，不同的成员如{0,1,2,3,4,5}，它只会执行一次跳转。

---

编辑：

为了使这个更像“插值搜索”，让我们同时移动上限和下限。同样的逻辑适用于两端：

public static int findZ(int[] a, int z){
    int j = 0;
    int k = a.length - 1;
    while(j <= k){
        if(a[j] == z)
            return j
        if(a[k] == z)
            return k;
        j += Math.abs(a[j] - z);
        k -= Math.abs(a[k] - z);
    }
    return -1;
}

它仍然以 O(n) 整体更坏的情况结束，但这对于插值搜索是正常的。

现在你最坏的情况更像{0,0,0,1,0,0,0}，你最好的情况更像{0,1,2,3,2,1,0}。