java - How can i fin the index using exponential, binary or interpolatin search recursively?

Question

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

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?.

static int binarySearch(int[] searchArray, int x) {
                    int start, end, midPt;
                    start = 0;
                    end = searchArray.length - 1;
                    while (start <= end) {
                            midPt = (start + end) / 2;
                            if (searchArray[midPt] == x) {
                                    return midPt;
                            } else if (searchArray[midPt] < x) {
                                    start = midPt + 1;
                            } else {
                                    end = midPt - 1;
                            }
                    }
                    return -1;
            }

Answer 1

您可以使用基本的二进制搜索算法。A[i]和A[i+1]最多相差 1的事实保证您会找到匹配项。

伪代码：

search(A, z):
  start := 0
  end := A.length - 1
  while start < end:
    x = A[start]
    y = A[end]
    mid := (start+end)/2
    if x <= z <= A[mid]:
      end := mid
    else if A[mid] < z <= y
      start := mid + 1
  return start

请注意，这不一定会返回第一个匹配项，但这不是必需的。

Answer 2

要应用您的算法，您需要一个排序数组。你的问题的条件是你有一个数组，它的元素与最大值 1 不同，不一定排序！！！

所以，这里是编写代码的步骤：

1. 检查问题数据是否符合给定条件
2. 对输入数组进行排序+保存旧索引值，以便稍后可以元素的初始位置
3. 以递归方式实现您的搜索方法
4. 二进制搜索源
5. 插值搜索源

这是完整的示例源：

public class Test {

// given start ======================================================
public int[] A = new int[] { 1, 1, 2, 3, 4, 4, 3, 2, 1, 1, 2, 3, 4, 5, 6,
        7, 8 };
public int z = 4;
// given end =======================================================

public int[] indexes = new int[A.length];

public static void main(String[] args) throws Exception {
    Test test = new Test();
    if (test.z < test.A[0] || test.z > test.A[test.A.length - 1]){
        System.out.println("Value z="+test.z+" can't be within given array");
        return;
    }
    sort(test.A, test.indexes);
    int index = binSearch(test.A, 0, test.A.length, test.z);
    if (index > -1) {
        System.out.println("Binary search result index =\t"
                + test.indexes[index]);
    }
    index = interpolationSearch(test.A, test.z, 0, test.A.length-1);
    if (index > -1) {
        System.out.println("Binary search result index =\t"
                + test.indexes[index]);
    }
}

public static void sort(int[] a, int[] b) {
    for (int i = 0; i < a.length; i++)
        b[i] = i;
    boolean notSorted = true;
    while (notSorted) {
        notSorted = false;
        for (int i = 0; i < a.length - 1; i++) {
            if (a[i] > a[i + 1]) {
                int aux = a[i];
                a[i] = a[i + 1];
                a[i + 1] = aux;
                aux = b[i];
                b[i] = b[i + 1];
                b[i + 1] = aux;
                notSorted = true;
            }
        }
    }
}

public static int binSearch(int[] a, int imin, int imax, int key) {
    // test if array is empty
    if (imax < imin)
        // set is empty, so return value showing not found
        return -1;
    else {
        // calculate midpoint to cut set in half
        int imid = (imin + imax) / 2;

        // three-way comparison
        if (a[imid] > key)
            // key is in lower subset
            return binSearch(a, imin, imid - 1, key);
        else if (a[imid] < key)
            // key is in upper subset
            return binSearch(a, imid + 1, imax, key);
        else
            // key has been found
            return imid;
    }
}

public static int interpolationSearch(int[] sortedArray, int toFind, int low,
        int high) {

    if (sortedArray[low] == toFind)
        return low;

    // Returns index of toFind in sortedArray, or -1 if not found
    int mid;

    if (sortedArray[low] <= toFind && sortedArray[high] >= toFind) {
        mid = low + ((toFind - sortedArray[low]) * (high - low))
                / (sortedArray[high] - sortedArray[low]); // out of range is
                                                            // possible here
        if (sortedArray[mid] < toFind)
            low = mid + 1;
        else if (sortedArray[mid] > toFind)
            // Repetition of the comparison code is forced by syntax
            // limitations.
            high = mid - 1;
        else
            return mid;
        return interpolationSearch(sortedArray, toFind, low, high);

    } else {
        return -1;
    }

}

}