Algorithm to find the mode in a unimodal array

Problem Detail: 

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?

Asked By : malhobayyeb

Answered By : rajaditya_m

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9888