Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:

n = A.length
if n == 1
    return 1

mid = floor(n/2)
if A[mid] < A[mid+ 1]
    return FIND_MODE(A[1 … mid])
    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?

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer

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.

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.