-3

∀i,0≤i≤n となる n 個の整数 A[0…n−1] の配列が与えられると、|A[i]−A[i+1]|≤1 となり、A[0 ]=x、A[n−1]=y、x<y です。指定された z の値に対して、A[j]=z、x≤ z ≤y となるようにインデックス j を見つけます。

問題がわかりません。私はそれに4日間立ち往生しています。バイナリ検索、指数検索、または補間検索を再帰的に使用する方法についてのアイデアはありますか? a [j] = z (aj) a [j] = z (aj) am i right? となるインデックス j を見つける要素 z が与えられます。

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

2 に答える 2

1

基本的な二分探索アルゴリズムを使用できます。A[i]との差が最大で 1 であるという事実はA[i+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

これは必ずしも最初の一致を返すとは限りませんが、必須ではありませんでした。

于 2013-10-02T18:25:01.613 に答える
0

アルゴリズムを適用するには、ソートされた配列が必要です。あなたの問題の状態は、必ずしもソートされていない、最大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;
    }

}

}
于 2013-10-02T19:29:41.737 に答える