rajhans
BAN USERHow about the following O(log n) solution:
public static int find_element(int[] array, int low, int up, int key) {
if(up==low) {
if(array[low] == key)
return low;
else
return -1;
}
int m = low+ (up-low)/2;
if(array[low] < array[mid] && (array[low] <= key) && array[mid] >= key)) {
// array[low..mid] is sorted and the element is in there
return find_element(array, low, mid, key);
}
if(array[low] > array[mid] && ((array[low] >= key) || array[mid] <= key)) {
// array[low..mid] is not sorted; however it is a rotated
// sorted array; also the remaining a[mid..up] contains
// element smaller than key or large than key
return find_element(array, low, mid, key);
}
//otherwise the element is in the second half
return find_element(array, mid+1, up, key);
}
How can the expected complexity (assuming the expectation is taken over the draw of random numbers in your algorithm and not some sort of a random draw of discs) be O(n log n), when the size of the output for some trivial cases is O(n^2)?
- rajhans February 23, 2013