在排序和旋转的数组中搜索 [英] Searching in a sorted and rotated array

问题描述

在准备面试时，我偶然发现了这个有趣的问题:

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

你得到了一个经过排序然后旋转的数组.

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

例如:

• 令arr = [1,2,3,4,5]，即已排序
• 向右旋转两次得到[4,5,1,2,3].

现在如何最好地在这个排序 + 旋转的数组中进行搜索?

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

可以对数组进行旋转，然后进行二分查找.但这并不比在输入数组中进行线性搜索更好，因为两者都是最坏情况的 O(N).

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

请提供一些指示.我在谷歌上搜索了很多关于这个的特殊算法，但找不到任何.

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) 中使用稍微修改的二进制搜索来完成.

This can be done in O(logN) using a slightly modified binary search.

有序+旋转数组的有趣特性是，当你将它分成两半时，两半中至少有一个会被排序.

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.

如果 mid 恰好是旋转点，它们的左右子数组都将被排序.

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.

一旦我们找到排序的那一半，我们就可以看到该键是否存在于那一半中 - 与极端情况进行简单比较.

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

如果密钥存在于那一半，我们递归地调用那一半的函数
否则我们在另一半递归调用我们的搜索.

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

伪代码:

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 half..search right half.
                else                 
                        return search(arr,key,mid+1,high)
                end-if

        // if right 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屋！