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)
Showing posts with label unimodal. Show all posts
Showing posts with label unimodal. Show all posts
Subscribe to:
Posts (Atom)
