algorithm - 需要一个特殊数组(线性场)的算法

Question

我有一个数组(线性场)预先排序的数字

 [1, 2, 3, 4, 5, 6],

但是这些数组y是右移(k次)，

现在是

[5,6,1,2,3,4], k = 2

但是我不知道k。只有数组A。

现在我需要一个算法来找到 A 中的最大值(运行时间为 O(logn))

我认为它与二进制搜索有关，任何人都可以帮助我吗？？

Answer 1

问题可以通过寻找“不连续点”来重述，即数组中 6, 1 点的索引。您可以使用类似于 binary search 的方法迭代地执行此操作，像这样:

取一个数组A和两个索引，low和high，初始设置为0和A.长度-1。不连续点在 low 和 high 之间。

将 (low, high) 分成两半。调用中点 mid。比较 A[low] 和 A[mid] 以及 A[mid] 和 A[high]。如果只有一对排序正确，则调整端点:如果排序的是 low-mid 对，则分配 low = mid，否则分配 high = mid。如果两个区间都是有序的，则答案是 A[high]。

这在 O(LogN) 中运行，因为每一步都会将问题的大小减半。