在准备面试时,我偶然发现了这个有趣的问题:
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++。
最佳答案
这可以使用稍微修改的二分搜索在 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
这里的关键是一个子数组总是会被排序,使用它我们可以丢弃数组的一半。
关于c++ - 在排序和旋转的数组中搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61678769/