二进制搜索以在旋转的排序列表中找到旋转点
问题内容：
我有一个旋转的排序列表，想对该列表进行二进制搜索以找到最小元素。
假设初始列表为{1,2,3,4,5,6,7,8}旋转列表可以像{5,6,7,8,1,2,3,4}
在这种情况下，普通的二进制搜索不起作用。任何想法如何做到这一点。
-编辑
我有另一个条件。如果列表未排序怎么办？
问题答案：
您只需要对二进制搜索算法进行一点修改；这是完整的可运行Java中的解决方案（有关Delphi实现的信息。
import java.util.*;
public class BinarySearch {
static int findMinimum(Integer[] arr) {
int low = 0;
int high = arr.length - 1;
while (arr[low] > arr[high]) {
int mid = (low + high) >>> 1;
if (arr[mid] > arr[high]) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
public static void main(String[] args) {
Integer[] arr = { 1, 2, 3, 4, 5, 6, 7 };
// must be in sorted order, allowing rotation, and contain no duplicates
for (int i = 0; i < arr.length; i++) {
System.out.print(Arrays.toString(arr));
int minIndex = findMinimum(arr);
System.out.println(" Min is " + arr[minIndex] + " at " + minIndex);
Collections.rotate(Arrays.asList(arr), 1);
}
}
}
打印：
[1, 2, 3, 4, 5, 6, 7] Min is 1 at 0
[7, 1, 2, 3, 4, 5, 6] Min is 1 at 1
[6, 7, 1, 2, 3, 4, 5] Min is 1 at 2
[5, 6, 7, 1, 2, 3, 4] Min is 1 at 3
[4, 5, 6, 7, 1, 2, 3] Min is 1 at 4
[3, 4, 5, 6, 7, 1, 2] Min is 1 at 5
[2, 3, 4, 5, 6, 7, 1] Min is 1 at 6
重复
请注意，重复项使得无法在中执行此操作O(log N)。考虑下面的位数组，其中包含many 1和一个0：
(sorted)
01111111111111111111111111111111111111111111111111111111111111111
^
(rotated)
11111111111111111111111111111111111111111111101111111111111111111
^
(rotated)
11111111111111101111111111111111111111111111111111111111111111111
^
可以按某种方式旋转此数组N，并且无法定位0in O(log N)，因为无法分辨它是在“中间”的左侧还是右侧。
我有另一个条件。如果列表未排序怎么办？
然后，除非您要先对其进行排序并从那里开始，否则必须进行线性搜索以找到最小值。
