Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). How do you find an element in the rotated array efficiently

public static int rotatedBinarySearch(int a[], int N, int key)

{

int low =0;

int high = N-1;

while(low <= high)

{

int mid = (L+R)/2;

if(a[mid] == key)

return mid;

//lower half is sorted

if(a[low] <= a[mid])

{

if(A[low]<= key && key < a[mid])

high = mid -1;

else

low = mid +1;

}

else // upper half is sorted

{

if(a[mid] < key && key < a[high])

low = mid + 1;

else

high = mid - 1;

}

}

return -1;

}

## No comments:

Post a Comment