由网友(哭过的眼睛看世界更清楚)分享简介：我有一个数组（线性场）其中pre排序号I have an Array (linear field)with pre sorted numbers [1, 2, 3, 4, 5, 6],但这些ARRA y是转移到右侧（k次），but these arra y is shift to the right (k ti...

我有一个数组（线性场） 其中pre排序号

I have an Array (linear field) with pre sorted numbers

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

但这些ARRA y是转移到右侧（k次），

but these arra y is shift to the right (k times),

现在它

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

但我不知道ķ。只有数组中的一个。

But I don´t know k. Only the array A.

现在我需要一个算法找到最大的A（与运行时间O（LOGN））

Now I need an Algorithm to find the max in A (with runtime O(logn))

我觉得它的东西与二进制搜索，谁能帮助我？

I think its something with binary search, can anyone help me??

推荐答案

的问题可以被重新表示在寻找不连续点的术语，即指数 6,1 点到数组中。你可以这样做反复使用类似的的的二进制搜索的，像这样的：

The question can be re-stated in terms of finding the "point of discontinuity", i.e the index of the 6, 1 spot in the array. You can do it iteratively using an approach similar to that of a binary search, like this:

取一个数组 A 键，两个指标，低和高，最初设置为 0 和则为a.length-1 。不连续的点之间低和高。

Take an array A and two indexes, low and high, initially set to 0 and A.Length-1. The spot of discontinuity is between low and high.

分割（低，高）一半。调用中点中期。比较 A [小] 到 A [MID] 和 A [MID] 到 A（高）。如果只有一对是正确排序，调整端点：如果它是一个的有序，分配中低对低=中等，否则分配高=中等。如果这两个区间是有序的，答案是 A（高）。

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].

这运行在 O（LOGN），因为每一步降低了问题的规模减半。

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