Monday, June 3, 2013

Find element in bitonic array

Given an array which is monotonically increasing and then decreasing . Write an algorithm to search for a given element. Expected algorithm O(Log n)

An array of number is bitonic if it consists of a strictly increasing sequence followed by a strictly decreasing sequence. We can solve the problem in 3logN comparisons by finding the maximum in the array and then doing two binary searches, one on the increasing and one on the decreasing sequence. The maximum can be found in Log N comparisons using binary search. Each step compares two adjacent numbers A[i] and A[i+1]. If hey are equal, they are both maximum. If A[i] is smaller, we restrict the search to indices at most i, if A[i+1] is bigger, we restrict the search to indices greater than i.


public static int getMaximumElement(int a[], int low, int high)
if(low == high) return high;
int mid = low + (high - low)/2;
if(a[mid] < a[mid+1])
return getMaximumElement(a, mid+1, high);
else if(a[mid] > a[mid+1])
return getMaximumElement(a, low, mid-1);
else return mid;

No comments: