2

ソートされた配列に複数のキーがあり、それらに対してバイナリ検索を実行したい場合、通常のバイナリ検索では、複数のオカレンスを持つキーのランダムインデックスが返されます。ここで、そのキーの最後のオカレンスのインデックスが必要です。 。

int data[] = [1,2,3,4,4,4,4,5,5,6,6];
int key = 4;
int index = upperBoundBinarySearch(data, 0, data.length-1, key);

Index Returned = 6
4

6 に答える 6

9

この回答の Java 実装は、キーの最初の出現を検出します。最後のオカレンスを見つけるためにこれを変更する方法についてのコメントがありますが、提案は無限ループになります。しかし、その考えは健全に思えます。

編集:いくつかの調査の後、The Algo Blog できちんとした解決策を見つけました。最初に見つかった一致が必要なものであるとは限らないため、これまでの「最適な」一致を追跡する必要があります。一致が得られたら、それを保存し、その一致の右側で二分探索を続けます ( low = mid + 1)。

public static int binarySearch(int[] a, int key) {
    return binarySearch(a, 0, a.length, key);
}

private static int binarySearch(int[] a, int fromIndex, int toIndex,
        int key) {
    int low = fromIndex;
    int high = toIndex - 1;
    int found = -1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = a[mid];

        if (midVal < key) {
            low = mid + 1;
        } else if (midVal > key) {
            high = mid - 1;
        } else {
            found = mid;
            // For last occurrence:
            low = mid + 1;
            // For first occurrence:
            // high = mid - 1;
        }
    }
    return found;
}

O(log n)この変更により、複雑さが維持されます。それでも、実際のパフォーマンスはアプリケーションによって異なります。配列の長さが検索対象のキーの重複の量よりもはるかに大きい場合、最後のオカレンスの線形検索の方が高速な場合があります。ただし、重複が多い場合は、この修正された二分探索がおそらく適しています。

于 2013-01-19T14:58:44.707 に答える
2

おそらく、O(log N)ソリューションが必要ですか? (それ以外の場合は、線形検索を実行できます。)

C++ では、(いくつかのうちの) 1 つの可能性は、std::upper_boundを使用することです。これにより、要求したものよりも大きい最初の要素への反復子が得られるため、前の要素を確認する必要があります。これは確かにO(log N)です。

Java がこれを標準ライブラリ メソッドとして提供しているかどうかはわかりません。ただし、 の疑似コードupper_boundは上記のリンクで提供されており、再実装するのに十分簡単なはずです。

于 2013-01-19T14:42:47.513 に答える
1

まあ、特に@Mattiasのおかげで、そのアルゴはいいですね。とにかく私は自分でやったことで、より良い結果が得られるように思えますが、アルゴ鉱山と@Mattiasの両方の複雑さを測定するのに誰かが助けてくれるか、誰かがより良い解決策を持っているなら、それは歓迎です....とにかく、ここに私が見つけた問題の解決策があります。

int upperBound(int[] array,int lo, int hi, int key)
{
    int low = lo-1, high = hi;
    while (low+1 != high)
    {
        int mid = (low+high)>>>1;
        if (array[mid]> key) high=mid;
        else low=mid;
    }
    int p = low;
    if ( p >= hi || array[p] != key )
        p=-1;//no key found
    return p;
}

これは最初のオカレンスです。また、他の同様の投稿で同じものを更新します。バイナリ検索での最初のオカレンス

int lowerBound(int[] array,int lo, int hi, int key)
{
    int low = lo-1, high = hi;
    while (low+1 != high)
    {
        int mid = (low+high)>>>1;
        if (array[mid]< key) low=mid;
        else high=mid;
    }
    int p = high;
    if ( p >= hi || array[p] != key )
        p=-1;//no key found
    return p;
}
于 2013-01-19T20:04:26.713 に答える
0

鍵を見つけたら。それを返す代わりに、配列を順次検索して最後の配列を取得します。これは O(N) ソリューションになります。

于 2013-01-19T15:02:14.260 に答える
-2

二分探索では、キーを配列 data[i] の要素と比較します。最後に一致したインデックスを取得するには、比較関数を変更して、key が data[i] および data[i+1] と等しい場合でも不等式になるようにする必要があります。

int upperBoundBinarySearch(int data[],int start, int end, int key) {
  while(start < end) {
    int middle = start + (end-start)/2;
    if (data[middle] == key && (middle == end || data[middle+1] != key))
      return middle;
    if (data[middle] > key)
      end = middle;
    else {
      if (start == middle)
        return start;
      start = middle;
    }
  }
  return start;
}
于 2013-01-19T14:52:00.587 に答える