algorithm - 在排序的可旋转数组中找到最小的数字

Question

我在一次采访中遇到了这个问题。请帮助我获得解决方案。

问题是:

You have sorted rotatable array, i. e. the array contains elements which are sorted and it can be rotated circularly, like if the elements in array are [5,6,10,19,20,29] then rotating first time array becomes [29,5,6,10,19,20] and on second time it becomes [20,29,5,6,10,19] and so on.

So you need to find the smallest element in the array at any point. You won’t be provided with number times array is rotated. Just given the rotated array elements and find out the smallest among them. In this case output should be 5.

Answer 1

方法一:

您可以在 O(logN) 时间内完成此操作。

使用修改后的二进制搜索找到旋转点，它是一个索引 i 使得
arr[i] > arr[i+1] .

例子:

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

两个子数组
(arr[1], arr[2], .., arr[i]) 和
(arr[i +1], arr[i+2], ..., arr[n]) 被排序。

答案是min(arr[1], arr[i+1])

方法二:

当您将排序后的旋转数组分成两半时 (arr[1],..,arr[mid]) 和 (arr[mid+1],.., arr[n])，其中一个总是排序的，另一个总是有最小值。我们可以直接使用修改后的二分搜索在未排序的一半中继续搜索

// index of first element
l = 0

// index of last element.
h = arr.length - 1

// always restrict the search to the unsorted 
// sub-array. The min is always there.
while (arr[l] > arr[h]) {
        // find mid.
        mid = (l + h)/2
        // decide which sub-array to continue with.
        if (arr[mid] > arr[h]) {
                l = mid + 1
        } else {
                h = mid
        }
}
// answer
return arr[l]