pg

Given an array of integers which is initially increasing and then decreasing, find the maximum value in the array.
Examples :

Input: arr[] = {8, 10, 20, 80, 100, 200, 400, 500, 3, 2, 1}
Output: 500

Input: arr[] = {1, 3, 50, 10, 9, 7, 6}
Output: 50

Corner case (No decreasing part)
Input: arr[] = {10, 20, 30, 40, 50}
Output: 50

Corner case (No increasing part)
Input: arr[] = {120, 100, 80, 20, 0}
Output: 120


Using binary search with a little bit change.
time complexity: O(log n)
The force brute way: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int findMaximum(vector<int>& array){
int i = 0;
int j = array.size()-1;
while(i <= j){
if(i == j)
return array[i];
if(i == j-1)
return array[i] > array[j] ? array[i] : array[j];
int mid = i + (j-i)/2;
if(mid-1 >= 0 && mid+1 < array.size()){
if(array[mid] > array[mid-1] && array[mid] > array[mid+1])
return array[mid];
else if(array[mid] > array[mid-1] && array[mid] < array[mid+1])
i = mid + 1;
else if(array[mid] < array[mid-1] && array[mid+1] < array[mid])
j = mid-1;
}
}
return -1;
}