arrays - 在已排序和旋转的数组中查找最小元素

Question

我最近遇到一个编程问题如下:

给定一个排序数组，数组在某个未知点旋转，我必须找到其中的最小元素。数组也可以包含重复项。

例如:

 Input: {5, 6, 1, 2, 3, 4}

 Output: 1  

 Input: {2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 1, 2}   

 Output: 0

我遵循的简单解决方案是遍历整个数组并找到最小值。此解决方案需要时间 O(n)。我理解一个事实，即最小元素是其前一个元素大于它的元素。如果不存在这样的元素，则没有旋转，第一个元素将是最小值。

但有人要求我提供 O(Logn) 解决方案。有没有办法在 O(Logn) 时间内解决？

Answer 1

在我的脑海中:

• 记下第一个条目
• 执行二进制搜索；在每个阶段，如果枢轴元素大于或等于存储的第一个元素，则选择右半部分；如果枢轴元素小于或等于存储的第一个元素，则选择左半部分。

例如，给定{4,5,6,7,1,2,3}:

• 以 7 > 4 为中心，减少到右半部分 {1,2,3}
• 以 2 <4 为中心，减少到左半部分 1。
• 只考虑一个元素，答案是1。