/* Find the maximum element in an array which is first
increasing and then decreasing.
Given an array of
integers which is initially increasing and then decreasing, find the maximum
value in the array. */
#include <limits>
int findPeak(int arr[], int start, int end) {
/* take care
of bad inputs */
if (end <
start) {
return std::numeric_limits<int>::min();
}
/* base case
1) end == start, only one element in the array, return this elt
2) end -
start == 1, two elts in the array, return the bigger one. */
if (end - start
< 2) {
return std::max(arr[start],
arr[end]);
}
int mid = (start
+ end) / 2;
/* mid elt
is the peak */
if (arr[mid]
> arr[mid-1] && arr[mid] > arr[mid+1]) {
return arr[mid];
}
/* mid elt
is not the peak && arr[mid] > arr[mid-1], meaning the peak is in the
second half of the array */
if (arr[mid]
> arr[mid-1]) {
return findPeak(arr, mid+1, end);
}
/* peak is
in the first half of the array */
return findPeak(arr, start,
mid-1);
}
No comments:
Post a Comment