# Algorithm to find the mode in a unimodal array

I am given the following problem in an Algorithms class:

Assume that you are given an array A[1 . . . n] of distinct numbers. You are told that the sequence of numbers in the array is unimodal, in other words, there is an index i such that the sequence A[1 . . . i] is increasing (A[j] < A[j + 1] for 1 ≤ j < i), and the sequence A[i . . . n] is decreasing. The index i is called the mode of A. Give an O(log n) algorithm that find the mode of A

I have written this draft solution as my solution but I want to make sure that this is an acceptable CORRECT solution.

My Algorithm:

FIND_MODE(A)
n = A.length
if n == 1
return 1

mid = floor(n/2)
if A[mid] < A[mid+ 1]
return FIND_MODE(A[1 … mid])
else
return mid + FIND_MODE(A[mid+1 … n])


Is it this acceptable and correct pseudocode algorithm?

Is it correct that this is a Big-O(log n) algorithm?

-

Almost correct. Just a small correction. It should be

if A[mid] > a[mid+1]


If two consecutive elements are increasing then they are in the increasing portion of the array, so the mode is to the right. Hence the correction.

-

There's a neat, provably "optimal" (in some sense) algorithm for this problem in Structure and interpretation of computer programs (free online version) by Abelson and Sussman. It involves partitioning the line in two pieces in a ratio $\phi$. I am not sure where the original algorithm came from in the literature, but maybe someone else can cite it.

-
ps am looking for an exact analysis of the runtime of this algorithm also. – vzn Feb 18 '13 at 23:46