我们希望在复杂度不大于 O(log n)
的循环排序数组中搜索给定元素 .
示例:在 {5,9,13,1,3}
中搜索 13
.
我的想法是将循环数组转换为常规排序数组,然后对结果数组进行二进制搜索,但我的问题是我提出的算法是愚蠢的,在最坏的情况下需要 O(n)
:
for(i = 1; i < a.length; i++){
if (a[i] < a[i-1]){
minIndex = i; break;
}
}
那么第i个元素的相应索引将由以下关系确定:
(i + minInex - 1) % a.length
很明显,我的转换(从循环到常规)算法可能需要O(n),所以我们需要一个更好的 .
根据ire_and_curses的想法,这是Java中的解决方案:
public int circularArraySearch(int[] a, int low, int high, int x){
//instead of using the division op. (which surprisingly fails on big numbers)
//we will use the unsigned right shift to get the average
int mid = (low + high) >>> 1;
if(a[mid] == x){
return mid;
}
//a variable to indicate which half is sorted
//1 for left, 2 for right
int sortedHalf = 0;
if(a[low] <= a[mid]){
//the left half is sorted
sortedHalf = 1;
if(x <= a[mid] && x >= a[low]){
//the element is in this half
return binarySearch(a, low, mid, x);
}
}
if(a[mid] <= a[high]){
//the right half is sorted
sortedHalf = 2;
if(x >= a[mid] && x<= a[high] ){
return binarySearch(a, mid, high, x);
}
}
// repeat the process on the unsorted half
if(sortedHalf == 1){
//left is sorted, repeat the process on the right one
return circularArraySearch(a, mid, high, x);
}else{
//right is sorted, repeat the process on the left
return circularArraySearch(a, low, mid, x);
}
}
希望这会奏效 .
16 回答
这是一个适用于Java的示例 . 由于这是一个排序数组,您可以利用它并运行二进制搜索,但需要稍微修改它以满足数据透视表的位置 .
该方法如下所示:
现在为了减轻烦恼,这里有一个很好的小类来验证算法:
那给你一个输出:
您只需使用简单的二进制搜索,就好像它是一个常规排序数组 . 唯一的技巧是你需要旋转数组索引:
其中start-index是圆形数组中第一个元素的偏移量 .
guirgis:发布一个面试问题很蹩脚,猜猜你没得到这份工作:-(
使用特殊的cmp函数,您只需要一次定期二进制搜索 . 就像是:
如果你可以依赖int下溢从每个元素中删除一个[0] - MIN_INT,并使用常规比较 .
您可以使用二进制搜索来查找最小元素的位置,并将其减少为O(Log n) .
你可以找到位置(这只是一个算法草图,它是不准确的,但你可以从中得到想法):
我< - 1
2. j < - n
3.而我<j
3.1 . k < - (j-i)/ 2
3.2 . 如果arr [k] <arr [i]则j < - k 3.3 . 否则我< - k
找到最小元素的位置后,您可以将该数组视为两个已排序的数组 .
虽然批准的答案是最佳的,但我们也可以使用类似和更清晰的算法 .
运行二进制搜索以查找pivot元素(旋转数组的位置) .
O(logn)
枢轴的左半部分将按降序排序,在此处运行向后二进制搜索以获得密钥 .
O(logn)
枢轴的右半部分将按递增顺序排序,在此半部分中为密钥运行前向二进制搜索 .
O(logn)
返回从步骤2和3找到的关键索引 .
总时间复杂度:
O(logn)
欢迎思考 .
不是很优雅,但是我的头顶 - 只需使用二分搜索来找到旋转阵列的枢轴,然后再次执行二分搜索,补偿枢轴的偏移 . 有点愚蠢地执行两次完整搜索,但它确实满足条件,因为O(log n)O(log n)== O(log n) . 保持简单和愚蠢(tm)!
对于搜索的低,中,高索引处的值,您有三个值
l
,m
,h
. 如果你认为你会继续寻找每种可能性:这是一个考虑目标值在哪里,并搜索一半空间的问题 . 最多一半的空间将包含在其中,并且很容易确定目标值是否在那一半或另一半 .
这是一个元问题 - 你是否认为二元搜索它是如何经常呈现的 - 在两点之间找到一个值,或者更一般地说是一个抽象搜索空间的重复划分 .
我想你可以使用这段代码找到偏移量:
简单的二进制搜索,稍有改动 .
旋转阵列索引=(i pivot)%size
pivot是索引i 1,其中a [i]> a [i 1] .
这是一个与二进制搜索相关的想法 . 只需继续为正确的数组索引绑定索引,左索引绑定将存储在步长中:
为了避免(pos == 1)的事情,我们可以循环备份(进入负数)并取(pos-1)mod n .
下面是使用二进制搜索的C实现 .
您可以通过利用数组排序的事实来实现此目的,除了数据透视值及其邻居之一的特殊情况 .
找到数组a的中间值 .
如果
a[0] < a[mid]
,则对数组前半部分中的所有值进行排序 .如果
a[mid] < a[last]
,则对数组后半部分中的所有值进行排序 .取出已排序的一半,并检查您的值是否在其中(与该半部分中的最大idx相比) .
如果是这样,只需二分之一搜索 .
如果没有,则必须是未分类的一半 . 拿这一半重复这个过程,确定那一半的哪一半被分类,等等
这是javascript中的解决方案 . 用几个不同的数组测试它似乎工作 . 它基本上使用ire_and_curses描述的相同方法:
Ruby
中的一个简单方法检查这个系数,