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


Popular posts from this blog