二进制搜索以在旋转的排序列表中查找旋转点

Question

我有一个已旋转的排序列表,并希望在该列表上进行二进制搜索以找到最小元素.

让我们假设初始列表是{1,2,3,4,5,6,7,8},旋转列表可以像{5,6,7,8,1,2,3,4}

在这种情况下,正常的二进制搜索不起作用.知道如何做到这一点.

- 编辑

我有另一个条件.如果列表没有排序怎么办？

Answer 1

只需对二进制搜索算法稍作修改即可; 这是完全可运行Java的解决方案(参见Serg对Delphi实现的回答,以及tkr对算法的可视化解释的答案).

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

也可以看看

• 带有数组的Java Collections.rotate()不起作用
  • 解释为什么Integer[]而不是int[]
• 谷歌研究博客:几乎所有的二进制搜索和合并都是破碎的
  • 解释为什么>>> 1而不是/ 2

重复

请注意,重复项使得无法执行此操作O(log N).考虑以下由多个1和一个组成的位数组0:

  (sorted)
  01111111111111111111111111111111111111111111111111111111111111111
  ^

  (rotated)
  11111111111111111111111111111111111111111111101111111111111111111
                                               ^

  (rotated)
  11111111111111101111111111111111111111111111111111111111111111111
                 ^

该阵列可以旋转N的方式,并定位0在O(log N)是不可能的,因为没有办法知道它是在"中间"的左侧或右侧.

我有另一个条件.如果列表没有排序怎么办？

然后,除非你想先排序并从那里开始,否则你必须进行线性搜索才能找到最小值.

也可以看看

• 维基百科| 选择算法| 线性最小/最大算法

Answer 2

这是一张图片来说明建议的算法: