搜索在排序和旋转阵列 [英] Searching in an sorted and rotated array

问题描述

在preparing为科技采访我偶然发现了这个有趣的问题：

While preparing for tech interview I stumbled upon this interesting question:

您已经得到了排序，然后旋转阵列。

You've been given an array that is sorted and then rotated.

例如

让改编= [1,2,3,4,5] 这是排序，然后旋转说两次向右给

Let arr = [1,2,3,4,5] which is sorted and then rotated say twice to the right to give

[4,5,1,2,3]

现在如何最好地在这一排序+旋转阵列一个搜索？

Now how best can one search in this sorted + rotated array ?

我们可以unrotate的数组，然后做一个二进制搜索。但它是没有比做输入阵列中的线性搜索更好，因为两者都是最坏情况下O（N）。

One can unrotate the array and then do a binary search. But it is no better than doing a linear search in the input array as both are worst case O(N).

请提供一些指引。我GOOGLE了很多特殊的算法可以实现，但找不到任何。

Please provide some pointers. I've googled a lot on special algorithms for this but couldn't find any.

据我了解C和C ++

I understand c and c++

推荐答案

这可以在使用稍微修改二进制搜索完成O（logN）的。

一分选+旋转阵列的有趣的特性是，当你把它分成两部分，用于至少一个两半的总是会来分类的。

The interesting property of a sorted + rotated array is that when you divide it into two halves, atleast one of the two halves will always be sorted.

Let input array arr = [4,5,6,7,8,9,1,2,3]
number of elements  = 9
mid index = (0+8)/2 = 4

[4,5,6,7,8,9,1,2,3]
         ^
 left   mid  right

作为似乎右子阵列是没有排序，而左子阵列进行排序。

as seem right sub-array is not sorted while left sub-array is sorted.

如果中间恰好是旋转点他们两个左和右子阵列将被排序。

If mid happens to be the point of rotation them both left and right sub-arrays will be sorted.

[6,7,8,9,1,2,3,4,5]
         ^

但在 无论如何一半（子阵列）必须进行排序的

But in any case one half(sub-array) must be sorted.

我们可以很容易地知道是哪一半是通过比较各一半的开始和结束的元素进行排序。

We can easily know which half is sorted by comparing start and end element of each half.

一旦我们发现其中有一半的排序，我们可以看到，如果关键是present的一半 - 与极端简单对比

Once we find which half is sorted we can see if the key is present in that half - simple comparison with the extremes.

如果关键是present的一半，我们递归调用函数的一半
否则，我们递归调用我们对另一半的搜索。

If the key is present in that half we recursively call the function on that half
else we recursively call our search on the other half.

我们正在放弃一半的阵列中的每个调用，这使得该算法 O（logN）的。

We are discarding one half of the array in each call which makes this algorithm O(logN).

伪code：

function search( arr[], key, low, high)

        mid = (low + high) / 2

        // key not present
        if(low > high)
                return -1

        // key found
        if(arr[mid] == key)
                return mid

        // if left half is sorted.
        if(arr[low] <= arr[mid]) {

                // if key is present in left half.
                if (arr[low] <= key && arr[mid] >= key) 
                        return search(arr,key,low,mid-1)

                // if key is not present in left hald..search right half.
                else                 
                        return search(arr,key,mid+1,high)
                end-if

        // if righ half is sorted. 
        else    
                // if key is present in right half.
                if(arr[mid] <= key && arr[high] >= key) 
                        return search(arr,key,mid+1,high)

                // if key is not present in right half..search in left half.
                else
                        return search(arr,key,low,mid-1)
                end-if
        end-if  

end-function

这里的关键是一个子阵列将始终进行排序，使用我们可以丢弃一半的阵列的

The key here is that one sub-array will always be sorted, using which we can discard one half of the array.

这篇关于搜索在排序和旋转阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！