An array A[1...n] is unimodal if it consists of an increasing sequence followed by a decreasing sequence. More precisely, if there is an index m in {1, 2, ... n} such that
A[i] < A[i+1] for 1 <= i < m and
A[i] > A[i+1] for m <= i < n
In particular, A[m] is the maximum element, and it is the unique "locally maximum" element surrounded by smaller elements.
Give an algorithm to compute the maximum element of a unimodal input array A[1...n] in O(lg n) time.
Source: Problem 1-3.from MIT OpenCourseWare Course - 6.046J / 18.410J Introduction to Algorithms (SMA 5503)
 
|
|
 
|
Subscribe to:
Post Comments (Atom)
2 comments:
Wont algo similar to binary search suffice?
Take the mid element of the array. Check whether it is greater than both its adjacent elements. If so, return that as result.
If the mid element is such that a[mid-1]<a[mid]<a[mid+1], recurse from a[mid] till the end.
In the third case, recurse from start till a[mid].
Madan
@Madan
Agree that solution looks perfect. Formally :
Let a => Unimodal Array (min size req to be 3)
s=0;
e=length(a) - 1;
loop_until_found:
if (e - s) == 0
//two elems left to compare
return NULL;
mid = (s+e+1)/2;
x = a[mid];
left = a[mid - 1];
right = a[mid + 1];
if left < x < right
//We are on the left side of the number to find.
s = mid;
elif left < x > right
// BINGO - this is that number
return x;
elif left > x < right
// We are on the right side of the number to find.
e = mid;
elif
// not possible for an unimodal array
return NULL;
goto loop_until_found;
Post a Comment