二分搜索在旋转排序列表中查找旋转点

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[]
• Google 研究博客：几乎所有二分搜索和合并排序都被破坏了
  • 解释为什么>>> 1 而不是 / 2

---

关于重复项

请注意，重复项使得不可能在 O(log N) 中完成此操作。考虑以下由许多 1 和一个 0 组成的位数组：

  (sorted)
  01111111111111111111111111111111111111111111111111111111111111111
  ^

  (rotated)
  11111111111111111111111111111111111111111111101111111111111111111
                                               ^

  (rotated)
  11111111111111101111111111111111111111111111111111111111111111111
                 ^

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

---

我还有另外一个条件。如果列表未排序怎么办？

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

另请参阅

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

Answer 2

下面是一张图片来说明建议的算法：

Answer 3

我想对该列表进行二分搜索以找到最小元素。
三元搜索适用于这种情况：当函数恰好有一个局部最小值时。

http://en.wikipedia.org/wiki/Ternary_search

编辑
在第二次阅读时，我可能误解了这个问题：函数不符合三元搜索的要求：/但是二元搜索不起作用吗？假设原始订单正在增加。

if (f(left) < f(middle)) 
    // which means, 'left' and 'middle' are on the same segment (before or after point X we search)
    // and also 'left' is before X by definition
    // so, X must be to the right from 'middle'
    left = middle
else
    right = middle

Answer 4

只需在 list - list[end] 上执行二分方法即可范围 [1, 结束)。二分法通过搜索符号变化来查找函数中的零，其运算时间复杂度为 O(log n)。

例如，

{5,6,7,8,1,2,3,4}→ {1,2,3,4,-3,-2,-1,0}

然后对该列表 {1,2,3,4,-3,-2,-1} 使用（离散）二分法。它将找到 4 和 -3 之间的零交叉点，该交叉点对应于您的旋转点。

Answer 5

Delphi 版本 - 第三个改进（感谢 Polygenelubricants 代码 - 但又删除了一个比较）变体：

type
  TIntegerArray = array of Integer;

function MinSearch(A: TIntegerArray): Integer;
var
  I, L, H: Integer;

begin
  L:= Low(A);   // = 0
  H:= High(A);  // = Length(A) - 1
  while A[L] > A[H] do begin
    I:= (L + H) div 2; // or (L + H) shr 1 to optimize
    Assert(I < H);
    if (A[I] > A[H])
      then L:= I + 1
      else H:= I;
  end;
  Result:= A[L];
end;

Answer 6

从列表 [first, last) 中选取一些子序列 [i,j]。 [i,j] 不包含不连续性，在这种情况下 *i <= *j，或者包含不连续性，在这种情况下剩余元素 (j, last) U [first, i) 已正确排序，在这种情况下 *j <= *i。

递归地二分可疑范围，直到筛选出一个元素。进行 O(log N) 比较。

Answer 7

我在 Java 中实现的二分搜索算法版本：

/**
 * Works only for arrays with NO duplicates.
 * Work also for zero-shifted array, e.g fully sorted, when shift = 0.
 */
public static int searchInShiftedArr(int[] arr, int key) {
    if (arr == null || arr.length == 0) {
        return -1;
    }
    int low = 0;
    int high = arr.length - 1;
    int mid; // declared outside loop to avoid constant memory allocation for this variable
    while (low <= high) {
        mid = (low + high) >>> 1; // same as "(low + high) / 2", but avoid negative overflow and should be faster than "low + (high - low)/2"
        if (arr[mid] == key) {
            return mid;
        }
        if (arr[low] <= arr[mid]) { // means left half of the array is sorted
            if (arr[low] <= key && key < arr[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        } else { // means right half of the array is sorted
            if (arr[mid] < key && key <= arr[high]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
    }
    return -1;
}

代码成功通过了 5000 个测试用例，所以我认为它已经准备好投入生产了。

Answer 8

如果我们想保持代码的简单性和可读性，递归是非常好的。但如果我们能够避免递归并仍然保持可读性，那就更好了，因为递归成本很大并且实际上不可扩展。

这是一个简单的迭代方法，其逻辑与上面讨论的非常相似（它利用二分搜索，添加小分区逻辑）。

private static int partitionSearch(int[] sortedArray, int numToFind) {
    if(sortedArray[0] > numToFind && sortedArray[sortedArray.length -1 ] < numToFind)
        return -1;
    boolean isInFirstPartition = sortedArray[0] <= numToFind;

    int startIndex = 0;
    int endIndex = sortedArray.length -1;
    int currentIndex;
    int currentValue;
    if(isInFirstPartition) { 
        do {
            currentIndex = (startIndex + endIndex) / 2;
            currentValue = sortedArray[currentIndex];
            if(currentValue == numToFind)
                return currentIndex;
            if(currentValue > sortedArray[startIndex] && sortedArray[currentIndex] < numToFind)
                startIndex = currentIndex + 1;
            else
                endIndex = currentIndex - 1;
        } while (startIndex <= endIndex);
    } else {
        do {
            currentIndex = (startIndex + endIndex) / 2;
            currentValue = sortedArray[currentIndex];
            if(currentValue == numToFind)
                return currentIndex;
            if(currentValue < sortedArray[endIndex] && sortedArray[currentIndex] > numToFind)
                endIndex = currentIndex - 1;
            else
                startIndex = currentIndex + 1;
        } while (startIndex <= endIndex);
    }
    return -1;
}

Answer 9

在 C++ 11 中，这个问题可以通过 partition_point 来解决：

std::vector<int> arr = {5,6,7,8,1,2,3,4};
auto rotation_point = std::partition_point(arr.begin(), std::prev(arr.end()),
    [&arr](int elem) { return elem > arr.back(); });

Answer 10

在 C++ 中，可以使用此代码（ O(log(n)) ）来获取旋转排序列表中的旋转次数：

findRotations(const vector<int> &A) {
    int len = A.size(), low = 0, high = len - 1, result = -1, target = A[len-1];

    while(low <= high){
        int  mid = low + (high-low)/2;
        if(A[mid] > target){
            low = mid + 1;
        }
        else{
            result = mid;
            high = mid - 1;
        }
    }

    return result;
}

如果列表未排序，您应该知道数组最初是什么，并且可以线性检查为旋转点 ( O(n) )。

Answer 11

像这样的东西可能会起作用（未经测试）：

//assumes the list is a std::vector<int> myList

int FindMinFromRotated(std::vector<int>::iterator begin, std::vector<int>::iterator end) {
    if (begin == end)
        throw std::invalid_argument("Iterator range is singular!");
    if (std::distance(begin, end) == 1) //What's the min of one element?
        return *begin;
    if (*begin < *end) //List is sorted if this is true.
        return *begin;
    std::vector<int>::iterator middle(begin);
    std::advance(middle, std::distance(begin, end)/2);
    if (*middle < *begin) //If this is true, than the middle element selected is past the rotation point
        return FindMinFromRotated(begin, middle)
    else if (*middle > *begin) //If this is true, the the middle element selected is in front of the rotation point.
        return FindMinFromRotated(middle, end)
    else //Looks like we found what we need :)
        return *begin;
}