在循环排序数组中搜索元素

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

希望这会奏效.

Answer 1

您可以通过利用数组排序的事实来实现此目的,除了pivot值的特殊情况和它的一个邻居之外.

• 找到数组a的中间值.
• 如果a[0] < a[mid],则对数组前半部分中的所有值进行排序.
• 如果a[mid] < a[last],则对数组后半部分中的所有值进行排序.
• 取出已排序的一半,并检查您的值是否在其中(与该半部分中的最大idx相比).
• 如果是这样,只需二分之一搜索一半.
• 如果没有,则必须是未分类的一半.取一半并重复此过程,确定该半部分的哪一半被分类等.

Answer 2

不是很优雅,但是我的头顶 - 只需使用二进制搜索来找到旋转阵列的枢轴,然后再次执行二进制搜索,补偿枢轴的偏移.有点愚蠢地执行两次完整搜索,但它确实满足条件,因为O(log n)+ O(log n)== O(log n).保持简单和愚蠢(tm)!

Answer 3

这是一个适用于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

Answer 4

你有三个值l,m,h在搜索的低,中,高指标的值.如果你认为你会继续寻找每种可能性:

// 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)  

这是一个考虑目标值在哪里,并搜索那一半空间的问题.最多一半的空间将包含在其中,并且很容易确定目标值是否在该一半或另一半中.

这是一个元问题 - 你是否认为二元搜索它是如何经常呈现的 - 在两点之间找到一个值,或者更一般地说是一个抽象搜索空间的重复划分.