I was listening to the peak find lecture from MIT and was confused as to why divide and conquer approach would work as the array is not sorted. It took me some time and a few examples to understand what is going on.
- The comparison at the mid point of array is not same as that of searching, but to check for the peak
- When we branch to the left (or right), we have already checked one side for the property of peakness, the other side remains to be checked.
- if the left (right) element is the only element, then it is the peak (trivial case)
- if not, we further sub-divide the problem and continue on the pieces with the same logic.
Basically, by having “greater than or equal to” in the definition of the peak, we are guaranteed to find a peak in any given array.