algorithm - ソートされた循環配列内の要素を検索する

Question

複雑さ以下の循環ソート配列内の特定の要素を検索したいと考えていますO(log n)。
例: を検索13し{5,9,13,1,3}ます。

私の考えは、循環配列を通常の並べ替えられた配列に変換し、結果の配列でバイナリ検索を行うことでしたが、私の問題は、私が思いついたアルゴリズムがO(n)最悪の場合にかかる愚かなことでした:

for(i = 1; i < a.length; i++){
    if (a[i] < a[i-1]){
        minIndex = i; break;
    }
}

次に、i 番目の要素の対応するインデックスは、次の関係から決定されます。

(i + minInex - 1) % a.length

私の変換 (循環から通常への) アルゴリズムが O(n) かかる可能性があることは明らかなので、より良いものが必要です。

ire_and_curses のアイデアによると、Java での解決策は次のとおりです。

public int circularArraySearch(int[] a, int low, int high, int x){
    //instead of using the division op. (which surprisingly fails on big numbers)
    //we will use the unsigned right shift to get the average
    int mid = (low + high) >>> 1;
    if(a[mid] == x){
        return mid;
    }
    //a variable to indicate which half is sorted
    //1 for left, 2 for right
    int sortedHalf = 0;
    if(a[low] <= a[mid]){
        //the left half is sorted
        sortedHalf = 1;
        if(x <= a[mid] && x >= a[low]){
            //the element is in this half
            return binarySearch(a, low, mid, x);
        }
    }
    if(a[mid] <= a[high]){
        //the right half is sorted
        sortedHalf = 2;
        if(x >= a[mid] && x<= a[high] ){
            return binarySearch(a, mid, high, x);
        }
    }
    // repeat the process on the unsorted half
    if(sortedHalf == 1){
        //left is sorted, repeat the process on the right one
        return circularArraySearch(a, mid, high, x);
    }else{
        //right is sorted, repeat the process on the left
        return circularArraySearch(a, low, mid, x);
    }
}

うまくいけば、これはうまくいくでしょう。

score 55 · Accepted Answer

これを行うには、ピボット値とその隣接値の特殊なケースを除いて、配列が並べ替えられているという事実を利用します。

配列の中央の値を見つけます。
の場合a[0] < a[mid]、配列の前半のすべての値が並べ替えられます。
の場合a[mid] < a[last]、配列の後半のすべての値が並べ替えられます。
ソートされた半分を取り、値がその中にあるかどうかを確認します（その半分の最大idxと比較してください）。
もしそうなら、その半分を二分探索するだけです。
そうでない場合は、分類されていない半分になっている必要があります。その半分を取り、このプロセスを繰り返して、その半分のどちらの半分がソートされているかを判断します。

score 9 · Accepted Answer

あまりエレガントではありませんが、頭から離れています-バイナリ検索を使用して、回転した配列のピボットを見つけてから、再度バイナリ検索を実行して、ピボットのオフセットを補正します。2 つの完全な検索を実行するのはばかげていますが、O(log n) + O(log n) == O(log n) であるため、条件は満たしています。シンプルで愚かな（tm）にしてください！

score 7 · Accepted Answer

これは Java で動作する例です。これはソートされた配列であるため、これを利用してバイナリ検索を実行しますが、ピボットの位置に合わせて少し変更する必要があります。

メソッドは次のようになります。

private static int circularBinSearch ( int key, int low, int high )
{
    if (low > high)
    {
        return -1; // not found
    }

    int mid = (low + high) / 2;
    steps++;

    if (A[mid] == key)
    {
        return mid;
    }
    else if (key < A[mid])
    {
        return ((A[low] <= A[mid]) && (A[low] > key)) ?
               circularBinSearch(key, mid + 1, high) :
               circularBinSearch(key, low, mid - 1);
    }
    else // key > A[mid]
    {
        return ((A[mid] <= A[high]) && (key > A[high])) ?
               circularBinSearch(key, low, mid - 1) :
               circularBinSearch(key, mid + 1, high);
    }
}

心配を軽減するために、アルゴリズムを検証する素敵な小さなクラスを次に示します。

public class CircularSortedArray
{
    public static final int[] A = {23, 27, 29, 31, 37, 43, 49, 56, 64, 78, 
                                   91, 99, 1, 4, 11, 14, 15, 17, 19};
    static int steps;

    // ---- Private methods ------------------------------------------

    private static int circularBinSearch ( int key, int low, int high )
    {
        ... copy from above ...
    }

    private static void find ( int key )
    {
        steps = 0;
        int index = circularBinSearch(key, 0, A.length-1);
        System.out.printf("key %4d found at index %2d in %d steps\n",
                          key, index, steps);
    }

    // ---- Static main -----------------------------------------------

    public static void main ( String[] args )
    {
        System.out.println("A = " + Arrays.toString(A));
        find(44);   // should not be found
        find(230);
        find(-123);

        for (int key: A)  // should be found at pos 0..18
        {
            find(key);
        }
    }
}

次の出力が得られます。

A = [23, 27, 29, 31, 37, 43, 49, 56, 64, 78, 91, 99, 1, 4, 11, 14, 15, 17, 19]
key   44 found at index -1 in 4 steps
key  230 found at index -1 in 4 steps
key -123 found at index -1 in 5 steps
key   23 found at index  0 in 4 steps
key   27 found at index  1 in 3 steps
key   29 found at index  2 in 4 steps
key   31 found at index  3 in 5 steps
key   37 found at index  4 in 2 steps
key   43 found at index  5 in 4 steps
key   49 found at index  6 in 3 steps
key   56 found at index  7 in 4 steps
key   64 found at index  8 in 5 steps
key   78 found at index  9 in 1 steps
key   91 found at index 10 in 4 steps
key   99 found at index 11 in 3 steps
key    1 found at index 12 in 4 steps
key    4 found at index 13 in 5 steps
key   11 found at index 14 in 2 steps
key   14 found at index 15 in 4 steps
key   15 found at index 16 in 3 steps
key   17 found at index 17 in 4 steps
key   19 found at index 18 in 5 steps

score 5 · Accepted Answer

検索の低、中、高のインデックスの値には、、の3lつの値があります。あなたがそうだと思うなら、あなたはそれぞれの可能性を探し続けるでしょう：mh

// normal binary search
l < t < m    - search(t,l,m)
m < t < h    - search(t,m,h)

// search over a boundary
l > m, t < m - search(t,l,m)
l > m, t > l - search(t,l,m)
m > h, t > m - search(t,m,h)  
m > h, t < h - search(t,m,h)

それは、目標値がどこにあるかを検討し、スペースのその半分を検索することの問題です。スペースの最大半分にラップオーバーが含まれ、ターゲット値がその半分にあるかどうかを簡単に判断できます。

それは一種のメタ質問です-二分探索はそれがどのように頻繁に提示されるかという用語だと思いますか-2点間の値を見つけるか、より一般的には抽象的な探索空間の繰り返し分割として。

score 0 · Accepted Answer

通常のソートされた配列であるかのように、単純なバイナリ検索を使用するだけです。唯一のトリックは、配列インデックスをローテーションする必要があることです。

(index + start-index) mod array-size

ここで、start-indexは、循環配列の最初の要素のオフセットです。

score 0 · Accepted Answer

このコーをチェックして、

    def findkey():
    key = 3

    A=[10,11,12,13,14,1,2,3]
    l=0
    h=len(A)-1
    while True:
        mid = l + (h-l)/2
        if A[mid] == key:
            return mid
        if A[l] == key:
            return l
        if A[h] == key:
            return h
        if A[l] < A[mid]:
            if key < A[mid] and key > A[l]:
                h = mid - 1
            else:
                l = mid + 1
        elif A[mid] < A[h]:
            if key > A[mid] and key < A[h]:
                l = mid + 1
            else:
                h = mid - 1

if __name__ == '__main__':
    print findkey()

score 0 · Accepted Answer

での簡単な方法Ruby

def CircularArraySearch(a, x)
  low = 0
  high = (a.size) -1

  while low <= high
    mid = (low+high)/2
    if a[mid] == x
      return mid
    end
    if a[mid] <= a[high]
      if (x > a[mid]) && (x <= a[high])
        low = mid + 1
      elsif high = mid -1
      end
    else
      if (a[low] <= x) && (x < a[mid])
        high = mid -1
      else
        low = mid +1
      end
    end
  end
  return -1
end

a = [12, 14, 18, 2, 3, 6, 8, 9]
x = gets.to_i
p CircularArraySearch(a, x)

score 0 · Accepted Answer

public static int _search(int[] buff, int query){
    int s = 0;
    int e = buff.length;
    int m = 0; 

    while(e-s>1){
        m = (s+e)/2;
        if(buff[offset(m)] == query){
            return offset(m);
        } else if(query < buff[offset(m)]){
            e = m;
        } else{
            s = m;
        }
    }

    if(buff[offset(end)]==query) return end;
    if(buff[offset(start)]==query) return start;
    return -1;
}

public static int offset(int j){
    return (dip+j) % N;
}

score 0 · Accepted Answer

二分探索を使用して最小要素の位置を見つけ、それをO(Log n)に減らすことができます。

次の方法で位置を見つけることができます (これはアルゴリズムの単なるスケッチであり、不正確ですが、そこからアイデアを得ることができます):
1. i <- 1
2. j <- n
3. while i < j
3.1. ｋ←（ジ）／２
３．２．もし arr[k] < arr[i] then j <- k 3.3. それ以外の場合は <- k

最小要素の位置を見つけたら、その配列を 2 つの並べ替えられた配列として扱うことができます。

score 0 · Accepted Answer

これは、二分探索に関連するアイデアです。右側の配列インデックスバウンドのインデックスをバックアップし続けるだけで、左側のインデックスバウンドがステップサイズに格納されます。

step = n
pos = n
while( step > 0 ):
    test_idx = pos - step   #back up your current position
    if arr[test_idx-1] < arr[pos-1]:
        pos = test_idx
    if (pos == 1) break
    step /= 2 #floor integer division
return arr[pos]

(pos==1) のことを避けるために、(負の数に入る) 循環的にバックアップし、(pos-1) mod n を取ることができます。

score 0 · Accepted Answer

少し変更した単純な二分探索。

回転配列のインデックス= (i+pivot)%size

ピボットは、a[i]>a[i+1] のインデックス i+1 です。

#include <stdio.h>
#define size 5
#define k 3
#define value 13
int binary_search(int l,int h,int arr[]){

int mid=(l+h)/2;

if(arr[(mid+k)%size]==value)
    return (mid+k)%size;

if(arr[(mid+k)%size]<value)
    binary_search(mid+1,h,arr);
else
    binary_search(l,mid,arr);
}

int main() {
    int arr[]={5,9,13,1,3};
    printf("found at: %d\n", binary_search(0,4,arr));
    return 0;
}

score -1 · Accepted Answer

guirgis: 面接の質問を投稿するのは下手です。あなたは仕事に就けなかったと思います :-(

特別な cmp 関数を使用すると、通常の二分探索で必要なパスは 1 つだけです。何かのようなもの：

def rotatedcmp(x, y):
  if x and y < a[0]:
    return cmp(x, y)
  elif x and y >= a[0]:
    return cmp(x, y)
  elif x < a[0]:
    return x is greater
  else:
    return y is greater

int アンダーフローに依存できる場合は、アクセス時に各要素から a[0] - MIN_INT を減算し、通常の比較を使用します。

algorithm - ソートされた循環配列内の要素を検索する

16 に答える 16

Related

Reference