在圆形排序的数组Seaching一个元素 [英] Seaching for an element in a circular sorted array

问题描述

我们要搜索​​一个给定的元素以圆形有序阵列中的复杂性并不比 O（log n）的更大。
示例：搜索 13 在 {5,9,13,1,3} 。

We want to search for a given element in a circular sorted array in complexity not greater than O(log n).
Example: Search for 13 in {5,9,13,1,3}.

我的想法是圆形数组转换成常规排序的数组然后做所产生的阵列上的二进制搜索，但我的问题是算法，我想出了是愚蠢的，它需要 O（N） 在最坏的情况：

My idea was to convert the circular array into a regular sorted array then do a binary search on the resulting array, but my problem was the algorithm I came up was stupid that it takes O(n) in the worst case:

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

然后第i个元素的相应索引将从以下关系来确定：

then the corresponding index of ith element will be determined from the following relation:

(i + minInex - 1) % a.length

很显然，我的转换（从圆形到正规）算法可能需要为O（n），所以我们需要一个更好的。

it is clear that my conversion (from circular to regular) algorithm may take O(n), so we need a better one.

据ire_and_curses的想法，这里是Java的解决方案：

According to ire_and_curses idea, here is the solution in 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);
    }
}

希望这会工作。

Hopefully this will work.

推荐答案

您可以通过利用一个事实，即数组排序，除了支点价值的特殊情况和它的邻国之一的优势做到这一点。

You can do this by taking advantage of the fact that the array is sorted, except for the special case of the pivot value and one of its neighbours.

• 找到的阵列。
的中间值
• 如果 A [0] LT;一个[MID] ，那么所有的值 第一阵列的一半是 排序。
• 如果 A [MID]＆LT;一个[最后] ，那么所有的 在对下半年的值 数组进行排序。
• 就拿排序 一半，并检查是否你的价值 就在于在它（比作 在半最大IDX）。
• 如果是这样，只是二进制 搜索一半。
• 如果不是这样，它 必须在未排序的一半。采取 一半并重复这一过程， 确定哪些一半一半 排序等。

• Find the middle value of the array a.
• If a[0] < a[mid], then all values in the first half of the array are sorted.
• If a[mid] < a[last], then all values in the second half of the array are sorted.
• Take the sorted half, and check whether your value lies within it (compare to the maximum idx in that half).
• If so, just binary search that half.
• If it doesn't, it must be in the unsorted half. Take that half and repeat this process, determining which half of that half is sorted, etc.

这篇关于在圆形排序的数组Seaching一个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！