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

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

让我们假设初始列表是{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种方式旋转，并且在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]上执行二分法 。 二分法通过搜索符号变化在函数中查找零，并在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

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

递归地将可疑范围分成两部分，直到你变成一个元素。 进行O（log N）比较。

Answer 7

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

 /** * Works only for arrays with NO duplicates. * Work also for zero-shifted array, eg 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个TestCases ，所以我认为它已经准备好了。

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

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

 //assumes the list is a std::vector myList int FindMinFromRotated(std::vector::iterator begin, std::vector::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::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; } 

Answer 10

在C ++ 11中，可以使用partition_point解决此问题：

 std::vector 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(); });