Unimodal array search
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: Design and analysis of algorithm Textbook
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: Design and analysis of algorithm Textbook
Comments
Post a Comment