我有一个数组（线性场）
与预先排序的数字
[1, 2, 3, 4, 5, 6],
但这些数组向右移动（k次），
now its
[5,6,1,2,3,4], k = 2
但我不知道k。只有数组A。
现在我需要一个算法来找到 A 中的最大值（运行时间 O(logn)）
我认为它是二分搜索的东西，任何人都可以帮助我吗？
这个问题可以用寻找“不连续点”来重新表述，即6, 1阵列中的点。您可以使用类似于二分查找 http://en.wikipedia.org/wiki/Binary_search_algorithm， 像这样：
取一个数组A和两个索引，low and high，初始设置为0 and A.Length-1。不连续点位于low and high.
Divide (low, high)一半。调用中点mid。比较A[low] to A[mid] and A[mid] to A[high]。如果只有一对正确排序，则调整端点：如果是low-mid已订购的对，分配low = mid，否则赋值high = mid。如果两个区间都已排序，则答案为A[high].
这运行在O(LogN)因为每一步都会将问题的规模缩小一半。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
