我有一个旋转的排序列表,并希望对该列表进行二进制搜索以找到最小元素。
让我们假设初始列表是 {1,2,3,4,5,6,7,8} 旋转列表可以像 {5,6,7,8,1,2,3,4}
在这种情况下,正常的二进制搜索不起作用。任何想法如何做到这一点。
- 编辑
我还有另一个条件。如果列表没有排序怎么办?
我有一个旋转的排序列表,并希望对该列表进行二进制搜索以找到最小元素。
让我们假设初始列表是 {1,2,3,4,5,6,7,8} 旋转列表可以像 {5,6,7,8,1,2,3,4}
在这种情况下,正常的二进制搜索不起作用。任何想法如何做到这一点。
- 编辑
我还有另一个条件。如果列表没有排序怎么办?
您只需要对二分搜索算法稍作修改即可;这是完整的可运行 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
Integer[]
而不是int[]
>>> 1
而不是/ 2
请注意,重复项使得无法在O(log N)
. 考虑以下由 many1
和 one组成的位数组0
:
(sorted)
01111111111111111111111111111111111111111111111111111111111111111
^
(rotated)
11111111111111111111111111111111111111111111101111111111111111111
^
(rotated)
11111111111111101111111111111111111111111111111111111111111111111
^
该数组可以以N
多种方式旋转,并且无法定位其中0
,O(log N)
因为无法判断它是在“中间”的左侧还是右侧。
我还有另一个条件。如果列表没有排序怎么办?
然后,除非您想先对其进行排序并从那里继续,否则您必须进行线性搜索以找到最小值。
这是一张图片来说明建议的算法:
我想对该列表进行二进制搜索以找到最小元素。
三元搜索将适用于这种情况:当函数恰好有一个局部最小值时。
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
只需在[1, end) 范围内执行二分法。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 之间找到一个零交叉点,这对应于您的旋转点。
[i,j]
选择列表的一些子序列[first, last)
。要么[i,j]
不包含不连续性,在这种情况下*i <= *j
,要么包含不连续性,在这种情况下,其余元素(j, last) U [first, i)
被正确排序,在这种情况下*j <= *i
。
递归地对可疑范围进行二分,直到您筛选到一个元素。进行 O(log N) 比较。
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;
如果我们想保持代码的简单性和可读性,递归是非常好的。但是,如果我们可以避免递归并仍然保持可读性,那就更好了,因为递归成本很高并且实际上不可扩展。
这是一个简单的迭代方法,其逻辑与上面讨论的差不多(它利用了二分搜索,添加了小分区逻辑)。
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;
}
我在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 个 TestCases,所以我认为它已经准备好生产了。
在 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(); });
在 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) )。
像这样的东西可能有效(未测试):
//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;
}