在Sorted Rotatable Array中查找最小数字

Question

我在一次采访中遇到了这个问题.请帮我解决问题.

问题是:

你有可旋转的阵列,i.即 数组包含已排序的元素,它可以循环旋转,就像数组中的元素是[5,6,10,19,20,29]然后旋转第一次数组成为[29,5,6,10,19] ,20]并且第二次变为[20,29,5,6,10,19],依此类推.

所以你需要在任何点找到数组中的最小元素.您将不会被提供数字时间数组旋转.只是给出旋转的数组元素并找出其中最小的元素.在这种情况下,输出应为5.

Answer 1

方法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])

方法2:

当排序,旋转阵列分为两半部分(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]