在经过排序和旋转的数组中搜索 [英] 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] 。

• Let arr = [1,2,3,4,5], which is sorted
• Rotate it twice to the right to give [4,5,1,2,3].

现在如何才能做到最好

一个人可以取消旋转数组，然后执行二进制搜索。但这并不比在输入数组中进行线性搜索好，因为它们都是最坏情况的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 ++。

推荐答案

可以使用稍微修改的二进制搜索在 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.

如果恰好是中点旋转，则将对左右两个子数组进行排序。

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屋！