Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers 2

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|improve this answer
add comment

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|improve this answer
    
ps am looking for an exact analysis of the runtime of this algorithm also. –  vzn Feb 18 '13 at 23:46
add comment

Your Answer

 
discard

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.