我们希望在不超过
例如:在
我的想法是将循环数组转换为常规排序数组,然后在结果数组上执行二分查找,但是我遇到的问题是我想出的算法在最坏情况下需要
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);
}
}
希望这会有效。