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.
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?