给定n整数A的阵列[0 ... N-1]，使得∀i，0≤i≤n，我们有| A [1] -A [I + 1] |≤1，并且如果A [0] = X，A [N-1] = Y，我们必须是x＆LT; Y。找到索引j使得A [J] = Z，用于z的给定值，x≤ž≤Y

Given an array of n integers A[0…n−1], such that ∀i,0≤i≤n, we have that |A[i]−A[i+1]|≤1, and if A[0]=x, A[n−1]=y, we have that x<y. Locate the index j such that A[j]=z, for a given value of z, x≤ z ≤y

我不明白这个问题。我一直停留在这4天。如何用二进制搜索，搜索指数或内插搜索递归地接近它的主意？我们给出的元素Z找到索引j，使得[J] = Z（AJ）是吗？

I dont understand the problem. I've been stuck on it for 4 days. Any idea of how to approach it with binary search, exponential search or interpolation search recursively? We are given an element z find the index j such that a [j] = z (a j) am i right?.

推荐答案

本：

| A [1] -A [I + 1] | ≤1

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

意味着在你的数组的每个元素会的最多一个不同的（-ve或+ VE）。那么它遵循了的最接近的索引，它可以包含的以Z 从电流 | A [CUR] - Z | 空间了。

means that each element in your array will be at most one different(-ve or +ve). It then follows that the closest index that can contain z from the current is |A[cur] - z| spaces away.

所以，你要做的就是以 J = 0 ，并计算出来的每一个步骤。跳转有很多空间，并再次检查。最终你会发现Z或到达终点。

So, what you do is start with j=0, and figure it out for each step. Jump that many spaces, and check again. Eventually you'll find z or reach the end.

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;
}

这是不是一个二进制或指数搜索，它不是递归的，但它的简单，就完事了。它可以作为一个片面的插值搜索。参阅下面的双向法。你可以把它变成一个递归函数，但应该是简单的，我会​​留给你。

This isn't a binary or exponential search, and it's not recursive, but it's simple and gets the job done. It works as a one-sided interpolation search. See below for the two-way method. You can turn it into a recursive function, but that should be straightforward and I'll leave that to you.

它运行在O（n），其中你最糟糕的情况下，性能将是对像 {0,0,0,0,1} ，它只能跳一步，并变成一条直线线性搜索。

It runs in O(n), where your worst case performance is going to be on something like {0,0,0,0,1}, where it can only jump one step, and turns into a straight linear search.

最好的情况下，将被责令，不同的成员如 {0,1,2,3,4,5} ，在那里将只执行一次跳跃。

Best case will be ordered, distinct members like {0,1,2,3,4,5}, where it will only perform one jump.

在使这个更插入搜索状，让我们在同一时间同时移动上下界的利益。同样的逻辑也适用于两端：

In the interests of making this more "interpolation search-like", let's move both the upper and lower bounds at the same time. The same logic applies for both ends:

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} 。

Now your worst case is more like {0,0,0,1,0,0,0}, and your best is like {0,1,2,3,2,1,0}.