227 1/3/2017 8:57:32 AM


:

Peak Finding -1D algorithms:

find_peak(a,low,high):

mid = (low+high)/2

if a[mid] < a[mid-1]

return find_peak(a,low,mid-1) // a peak must exist in A[low..mid-1]

else if a[mid] < a[mid+1]

return find_peak(a,mid+1,high) // a peak must exist in A[mid+1..high]

else 

​return mid // this is a peak;

:

This is a recursive algorithm.

General design technique:

1. Divide input into part(s)

2. Conquer each part recursively

3. Combine result(s) to solve original problem

 

Other approach:

  • If a[n/2] < a[n/2 − 1] then only look at left half 1 . . . n/2 − − − 1 to look for peak
  • Else if a[n/2] < a[n/2 + 1] then only look at right half n/2 + 1 . . . n to look for peak
  • Else n/2 position is a peak
:

O(log n)