c++ - 在排序和旋转的数组中搜索

Question

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

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

For example:

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

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

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

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

我了解 C 和 C++。

Answer 1

这可以在 O(logN) 中使用稍微修改的二进制搜索来完成。

排序+旋转数组的有趣特性是，当您将其分成两半时，两半中至少有一个将始终被排序。

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

似乎右子数组未排序，而左子数组已排序。

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

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

但在任何情况下，一半(子数组)都必须排序。

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

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

如果键存在于那一半，我们递归调用那一半的函数
否则我们递归调用另一半的搜索。

我们在每次调用中丢弃一半的数组，这使得这个算法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

这里的关键是一个子数组总是被排序的，使用它我们可以丢弃一半的数组。