在圆形排序数组中搜索元素 [英] Searching for an element in a circular sorted array

问题描述

我们要在圆形排序数组中搜索给定元素，其复杂度不超过 O（log n）。

示例：搜索 {5,9,13,1,3} 中的 13 。

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

希望这会起作用。

推荐答案

您可以利用数组已排序的事实来实现此目的，但支点值及其邻居之一的特殊情况除外。

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的中间值。


• 如果 a [0]< a [mid] ，则对数组前半部分
  中的所有值进行排序。


• 如果 a [mid]< a [last] ，然后对
  数组后半部分的所有
  值进行排序。


• 取已排序的
  一半，并检查您的值
  是否在其中（与那一半中的
  最大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.

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