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

Question

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

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

在这种情况下，正常的二分搜索不起作用。任何想法如何做到这一点。

-- 编辑

我还有另一种情况。如果列表没有排序怎么办？？

Answer 1

您只需要对二分搜索算法稍作修改即可；这是完整的可运行 Java 的解决方案(参见 Serg's answer 了解 Delphi 实现，tkr's answer 了解算法的直观解释)。

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() with an array doesn’t work
  • 解释为什么使用 Integer[] 而不是 int[]
• Google Research Blog: Nearly All Binary Searches and Mergesorts are Broken
  • 解释为什么用 >>> 1 而不是 /2

---

关于重复

请注意，重复项使得在 O(log N) 中无法做到这一点。考虑以下由许多 1 和一个 0 组成的位数组:

  (sorted)
  01111111111111111111111111111111111111111111111111111111111111111
  ^

  (rotated)
  11111111111111111111111111111111111111111111101111111111111111111
                                               ^

  (rotated)
  11111111111111101111111111111111111111111111111111111111111111111
                 ^

这个数组可以N方式旋转，在O(log N)中定位0是不可能的，因为没有办法判断它是在“中间”的左侧还是右侧。

---

I have one another condition. What if the list is not sorted??

然后，除非您想先对其进行排序并从那里继续，否则您必须进行线性搜索以找到最小值。

另见

• Wikipedia | Selection algorithm | Linear minimum/maximum algorithms