二进制搜索找到一个旋转的排序列表中的旋转点 [英] Binary search to find the rotation point in a rotated sorted list

问题描述

我有被旋转的排序列表，并希望做一个二进制搜索在名单上找到的最小元素。

I have a sorted list which is rotated and would like to do a binary search on that list to find the minimum element.

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

Lets suppose initial list is {1,2,3,4,5,6,7,8} rotated list can be like {5,6,7,8,1,2,3,4}

普通的二进制搜索不会在这种情况下工作。任何想法如何做到这一点。

Normal binary search doesn't work in this case. Any idea how to do this.

- 修改

我有一个其他条件。如果什么列表未排序??

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

推荐答案

在二进制搜索算法一个稍微的改变是你所需要的;这里是完全可运行的Java解决方案（见<一href="http://stackoverflow.com/questions/2796413/binary-search-to-find-the-rotation-point-in-a-rotated-sorted-list/2796523#2796523">Serg's回答德尔福实施，<一个href="http://stackoverflow.com/questions/2796413/binary-search-to-find-the-rotation-point-in-a-rotated-sorted-list/2797181#2797181">tkr's回答的算法直观的解释）。

A slight modification on the binary search algorithm is all you need; here's the solution in complete runnable Java (see Serg's answer for Delphi implementation, and tkr's answer for visual explanation of the algorithm).

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

另请参见

• <一个href="http://stackoverflow.com/questions/2794950/java-collections-rotate-with-an-array-doesnt-work/">Java Collections.rotate（）与数组不起作用
  • 解释了为什么整数[] 而不是 INT []

  See also

  • Java Collections.rotate() with an array doesn’t work
    • Explains why Integer[] instead of int[]
    • 解释了为什么＆GT;＆GT;＆GT; 1 而不是 / 2
    • Explains why >>> 1 instead of / 2

    注意，复制就不可能做到这一点的 O（日志N）。请看下面的位阵列由许多的 1 ，一个 0 ：

    Note that duplicates makes it impossible to do this in O(log N). Consider the following bit array consisting of many 1, and one 0:

      (sorted)
      01111111111111111111111111111111111111111111111111111111111111111
      ^
    
      (rotated)
      11111111111111111111111111111111111111111111101111111111111111111
                                                   ^
    
      (rotated)
      11111111111111101111111111111111111111111111111111111111111111111
                     ^
    

    这数组可以在 N为旋转的方式，和定位 0 在 0 （日志N）是不可能的，因为没有办法知道它是在中间的左侧或右侧。

    This array can be rotated in N ways, and locating the 0 in O(log N) is impossible, since there's no way to tell if it's in the left or right side of the "middle".

    我有一个其他条件。如果什么列表未排序??

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

    那么，除非你想先排序，并从那里出发，你就必须做一个线性搜索找到了最低程度。

    Then, unless you want to sort it first and proceed from there, you'll have to do a linear search to find the minimum.

    • <一个href="http://en.wikipedia.org/wiki/Selection_algorithm#Linear_minimum.2Fmaximum_algorithms">Wikipedia |选择算法|线性最小/最大算法

    这篇关于二进制搜索找到一个旋转的排序列表中的旋转点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！