For an array a: a1, a2, … ak, … an, ak is a peak if and only if ak-1 ≤ ak ≥ ak+1 when 1 < k and k < n. a1 is a peak if a1 ≥ a2, and an is a peak if an-1 ≤ an. The goal is to find one peak from the array.
A divide and conquer algorithm is given as follows:
find_peak(a,low,high):
mid = (low+high)/2
if a[mid-1] <= a[mid] >= a[mid+1] return mid // this is a peak;
if a[mid] < a[mid-1]
return find_peak(a,low,mid-1) // a peak must exist in A[low..mid-1]
if a[mid] < a[mid+1]
return find_peak(a,mid+1,high) // a peak must exist in A[mid+1..high]
Why this algorithm is correct? I think it may suffer from losing half of the array in which a peak exists.