java 二分法查找旋转排序列表中的旋转点

Binary search to find the rotation point in a rotated sorted list

提问by Boolean

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

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

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}

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

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

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

-- Edit

- 编辑

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

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

回答by polygenelubricants

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

您只需要对二进制搜索算法稍作修改即可；这是完整的可运行 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);
        }
    }
}

This prints:

这打印：

[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

See also

也可以看看

• Java Collections.rotate() with an array doesn't work
  • Explains why Integer[]instead of int[]
• Google Research Blog: Nearly All Binary Searches and Mergesorts are Broken
  • Explains why >>> 1instead of / 2

• 带有数组的 Java Collections.rotate() 不起作用
  • 解释为什么Integer[]而不是int[]
• 谷歌研究博客：几乎所有的二分搜索和归并排序都被破坏了
  • 解释为什么>>> 1而不是/ 2

---

---

On duplicates

关于重复

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:

请注意，重复项使得在O(log N). 考虑以下由 many1和 one组成的位数组0：

  (sorted)
  01111111111111111111111111111111111111111111111111111111111111111
  ^

  (rotated)
  11111111111111111111111111111111111111111111101111111111111111111
                                               ^

  (rotated)
  11111111111111101111111111111111111111111111111111111111111111111
                 ^

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

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

---

---

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.

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

See also

也可以看看

• Wikipedia | Selection algorithm | Linear minimum/maximum algorithms

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

回答by tkr

Here is a picture to illustrate the suggested algorithms:

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

回答by Nikita Rybak

I would like to do a binary search on that list to find the minimum element.
Ternary search will work for such case: when function has exactly one local minimum.

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

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

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

editUpon second reading, I probably misunderstood the question: function does not conform requirements for ternary search :/ But won't binary search work? Suppose, original order was increasing.

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

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

回答by rlbond

Just perform the bisection methodon list - list[end]over the range [1, end). The bisection method looks for zeros in a function by searching for a sign change, and operates in O(log n).

只需在[1, end) 范围内执行二分法list - list[end]。二分法通过搜索符号变化来查找函数中的零点，并在 O(log n) 中进行运算。

For example,

例如，

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

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

Then use the (discretized) bisection method on that list {1,2,3,4,-3,-2,-1}. It will find a zero crossing between 4 and -3, which corresponds to your rotation point.

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

回答by Potatoswatter

Pick some subsequence [i,j]of the list [first, last). Either [i,j]does not contain the discontinuity, in which case *i <= *j, or it does, in which case the remaining elements (j, last) U [first, i), are properly sorted, in which case *j <= *i.

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

Recursively bipartition the suspect range until you winnow down to one element. Takes O(log N) comparisons.

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

回答by kludg

Delphi version - third improved (thanks to polygenelubricants code - yet one more comparison removed) variant:

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;

回答by user1710310

Recursion is very good if we want to maintain simplicity and readability of the code. But if we can avoid recursion and still maintain the readability, it would be better because recursion cost is significant and not actually scalable.

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

Here is a simple iterativemethod with logic pretty much as discussed above ( it's taking advantage of binary search, adding small partition logic).

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

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;
}

回答by HitOdessit

My version of binary search algorithm implementation in Java:

我在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;
}

Code successfully passed 5000 TestCases, so I think it's production ready.

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

回答by sakra

In C++ 11, this problem can be solved with partition_point:

在 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(); });

回答by Billy ONeal

Something like this might work (Not tested):

像这样的事情可能会起作用（未测试）：

//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;
}