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

Question

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

你得到了一个排序然后旋转的数组。

例如：

• 让 arr = [1,2,3,4,5] ，这是排序的
• 向右旋转两次以给出 [4,5,1,2,3] 。

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

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

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

我了解 C 和 C++。

原文由 Jones 发布，翻译遵循 CC BY-SA 4.0 许可协议

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

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

原文由 codaddict 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

在 O(logN) 复杂性中，有一个简单的想法可以解决这个问题。这个想法是，

If the middle element is greater than the left element, then the left part is sorted. Otherwise, the right part is sorted 。

一旦确定了排序部分，您只需检查该值是否属于该排序部分。如果没有，您可以划分未排序的部分并从中找到已排序的部分（未排序的部分）并继续二进制搜索。

例如，考虑下图。数组可以左旋或右旋。

下图显示了中间元素与最左边元素的关系，以及这与数组的哪一部分是纯排序的。

如果您看到图像，您会发现中间元素 >= 左侧元素，在这种情况下，左侧部分是纯排序的。

数组可以左旋转多次，例如一次、两次、三次等。下图显示，对于每次旋转， if mid >= left, left part is sorted 的属性仍然有效。

更多图片解释可以在下面的链接中找到。 （免责声明：我与此博客相关联） https://foolishhungry.com/search-in-rotated-sorted-array/ 。

希望这会有所帮助。

快乐编码！ :)

原文由 late_riser 发布，翻译遵循 CC BY-SA 4.0 许可协议