Lone Pine Canyon, California.
Given a array that's sorted but rotated at some unknown pivot, in which all elements are distinct, find a "peak" element in O(log N) time.
An element is considered a peak if it is greater than both its left and right neighbors. It is guaranteed that the first and last elements are lower than all others.
Understanding the problem
This is very similar to an earlier problem that I encountered a few days ago.In this problem a sorted array has been rotated once. Elements after a certain index are removed and prepended to the beginning of the array.
The objective here is to figure out the peak. The peak is the last element in the original sorted array
High level solution
The solution is very similar to the binary search solution in the earlier problem . The problem even hints at this - log(N) , which is a factor in binary search algorithm's runtime.
Therefore, the solution to this question lies in
- Splitting the array
- Validating that the middle element does not meet our solution's requirement
- Recursively check the resultant sub-arrays.
In the following example, 9 is the middle element and it does not meet the requirement of a peak. It is not greater than the next element, so it can be eliminated
We have to divide the array into two sub-arrays, and continue to recursively check them.
Optimization
A sub-array that is sorted is guaranteed to not contain a peak. We can therefore further optimize the solution, by eliminating these sub-arrays.
In the example, the left sub-array can be ignored because it is already sorted. This can be determined by comparing the first and last elements of the sub-array. However, the right sub-array starts with 10 and ends with 3. It therefore needs to be considered when checking for a peak.
Psuedocode
Here is some quick pseudocode, that describes the solution above -
