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

Question

我有一个带有预排序数字的数组（线性字段）

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

但是这些数组向右移动（k 次），

现在它

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

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

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

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

Answer 1

这个问题可以重新表述为寻找“不连续点”，即6, 1阵列中点的索引。您可以使用类似于二分搜索的方法迭代地执行此操作，如下所示：

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

Divide (low, high) in half. Call the midpoint mid. Compare A[low] to A[mid] and A[mid] to A[high]. If only one pair is ordered correctly, adjust the endpoint: if it's the low-mid pair that's ordered, assign low = mid, otherwise assign high = mid. If both intervals are ordered, the answer is A[high].

This runs in O(LogN) because each step reduces the size of the problem in half.

Answer 2

你是对的，它基本上是一个二进制搜索。

选择中间的数字。如果它小于（当前分区的）左端的数字，那么最大的数字在左分区中。否则，它在正确的分区中。

Answer 3

如果您知道“k”是什么，那么您可以拆分数组并重新构建它，或者您可以重新实现偏移 k 的二进制搜索算法。

例如，

int low = 0;
int high = array.length - 1;

while(low != high)
{
    int test = (low + high)/2;
    int testIndex = (test + k) % array.length;
    if (array[testIndex] < wanted)
        low = test;
    else if (array[testIndex] > wanted)
       high = test;
    else
       return testIndex;
 }

或类似的东西。testIndex 变量偏移了“k”，但搜索索引（低、高和测试）不知道这一点。

PS.，您需要在此代码中添加更多安全检查（例如，“想要”不在数组中）；我只是想显示索引偏移部分。