24

まず、この質問のビットニック配列はK、長さの配列のインデックスに対して、0 から K までNが0 < K < N - 1単調に増加する整数のシーケンスであり、K から N - 1 までが単調に減少する整数のシーケンスであるようなものとして定義されます。

例: [1, 3, 4, 6, 9, 14, 11, 7, 2, -4, -9]. 1 から 14 まで単調に増加し、14 から -9 まで減少します。

この問題の前段階は、 で解くこと3log(n)です。これははるかに簡単です。最大値のインデックスを見つけるために 1 回のバイナリ検索を変更し、次に 0 から K まで、K + 1 から N - 1 までの 2 つのバイナリ検索をそれぞれ行います。

の解決策で2log(n)は、最大のインデックスを見つけずに問題を解決する必要があると思います。二分探索をオーバーラップすることを考えましたが、それ以上に先に進む方法がわかりません。

4

8 に答える 8

1

このアルゴリズムは、バイトニック検索とバイナリ検索を組み合わせることで再帰的に機能します。

def bitonic_search (array, value, lo = 0, hi = array.length - 1)
  if array[lo] == value then return lo
  if array[hi] == value then return hi
  mid = (hi + lo) / 2
  if array[mid] == value then return mid
  if (mid > 0 & array[mid-1] < array[mid])
     | (mid < array.length-1 & array[mid+1] > array[mid]) then
    # max is to the right of mid
    bin = binary_search(array, value, low, mid-1)
    if bin != -1 then return bin
    return bitonic_search(array, value, mid+1, hi)
  else # max is to the left of mid
    bin = binary_search(array, value, mid+1, hi)
    if bin != -1 then return bin
    return bitonic_search(array, value, lo, mid-1)

したがって、時間の再帰式は、二分探索から来るf(l) = f(l/2) + log(l/2) + c場所であり、関数本体で行われる比較のコストです。log(l/2)c

于 2013-10-15T04:13:50.583 に答える
0

配列の最大要素がどこにあるか、および中間要素が目的の値より大きいかどうかに応じて、5 つの主なケースがあります。

中間要素を計算します。検索終了と一致する場合は、中間要素の目的の値を比較します。それ以外の場合は、次の手順に進みます。

  1. 中央の要素を隣接要素と比較して、最大要素が左または右にあるかどうかを確認します。両方の隣接要素が中央の要素よりも小さい場合、要素は配列に存在しないため、終了します。

  2. 中央の要素が目的の値よりも小さく、最大要素が右側にある場合は、右側の部分配列でバイトニック検索を実行します

  3. 中央の要素が目的の値よりも小さく、最大要素が左側にある場合、左側の部分配列でバイトニック検索を実行します

  4. 中央の要素が目的の値よりも大きく、最大要素が左側にある場合は、右側の部分配列で降順二分探索を実行します

  5. 中央の要素が目的の値よりも大きく、最大要素が右側にある場合は、左側のサブ配列で昇順のバイナリ検索を実行します

最悪の場合、配列が半分に分割されるたびに 2 つの比較を行うことになるため、複雑さは 2*logN になります。

于 2016-12-13T20:25:02.297 に答える
-2

バイナリ分割には、次の 3 つのケースがあります。

  1. max item が右、バイナリ検索が左、bitoinc 検索が右です。
  2. 左が最大アイテム、右がバイナリ検索、左が bitoinc 検索です。
  3. 最大アイテムは正確に分割ポイントにあり、次に左右両方のバイナリです。

注意: 昇順/降順のため、左と右で使用される二分探索は異なります。

public static int bitonicSearch(int[] a, int lo, int hi, int key) {
    int mid = (lo + hi) / 2;
    int now = a[mid];
    if (now == key)
        return mid;
    // deal with edge cases
    int left = (mid == 0)? a[mid] : a[mid - 1];
    int right = (mid == a.length-1)? a[mid] : a[mid + 1];
    int leftResult, rightResult;
    if (left < now && now < right) { // max item is at right
        leftResult = binarySearchIncreasing(a, lo, mid - 1, key);
        if (leftResult != -1)
            return leftResult;
        return bitonicSearch(a, mid + 1, hi, key);
    }
    else if (left > now && now > right) { // max item is at left
        rightResult = binarySearchDecreasing(a, mid + 1, hi, key);
        if (rightResult != -1)
            return rightResult;
        return bitonicSearch(a, lo, mid - 1, key);
    }
    else { // max item stands at the split point exactly
        leftResult = binarySearchIncreasing(a, lo, mid - 1, key);
        if (leftResult != -1)
            return leftResult;
        return binarySearchDecreasing(a, mid + 1, hi, key);
    }
}
于 2014-02-11T09:13:27.277 に答える