# Find the maximum element in an array which is first increasing and then decreasing

In this article, we are going to see how to search the maximum element of an array which is first increasing & then decreasing. This maximum element in such type of array is also known as peak element.
Submitted by Radib Kar, on February 03, 2021

Say, the array is like below,

[3, 10, 17, 15, 2, -3]

Then the peak element or the maximum element would be 17.

We can solve this both by linear search & binary search. The linear search algorithm will have the worst case time complexity of O(n) & the binary search algorithm will have worst-case time complexity of O(logN).

Using linear search

Since the array is increasing first & then decreasing so the maximum element would be the last one in the increasing series & the first one in the decreasing series. SO we can ignore the increasing part and check if the next element is decreasing or not. As soon as we find any element is greater than it's immediate next element on the right side, we can infer that as the peak element. The algorithm would ve like below,

```for (int i = 1; i < arr.size(); i++) {
if (arr[i] > arr[i + 1]) {
peakNumber = arr[i];
break;
}
}
```

Using Binary Search

We can also solve this using binary search. We need to check whether our pivot element is in the increasing part or the decreasing part. If the pivot element is in the increasing part then we need to search only in the right part & if it's in the decreasing part then we need to search in the left part. The implementation is like following,

```int findThePeakEfficientRecur(vector& arr, int start, int end)
{
//base cases
//only one element in array

if (start == end)
return arr[start];
//if two element
if (start + 1 == end) {
return max(arr[start], arr[end]);
}

int mid = start + (end - start) / 2;

//we got our peak
if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1])
return arr[mid];
//pivot element is still in the increasing part
else if (arr[mid] > arr[mid - 1] && arr[mid] < arr[mid + 1]) {
return findThePeakEfficientRecur(arr, mid + 1, end);
}
else
return findThePeakEfficientRecur(arr, start, mid - 1);
}
```

C++ Implementation:

```#include <bits/stdc++.h>
using namespace std;

//naive approach
void findThePeakNaive(vector<int>& arr)
{
cout << "..............Using naive search......\n";

//O(n) time complexity

int peakNumber = -1;
//if only one element
if (arr.size() == 1)
peakNumber = arr[0];
//if two elements
if (arr.size() == 2)
peakNumber = max(arr[0], arr[1]);
for (int i = 1; i < arr.size(); i++) {
if (arr[i] > arr[i + 1]) {
peakNumber = arr[i];
break;
}
}
if (peakNumber == -1)
cout << "There is no peak element in this array\n";
else
cout << "The peak element(maximum number) is " << peakNumber << "\n";

return;
}

//recursive binary search
int findThePeakEfficientRecur(vector<int>& arr, int start, int end)
{
//base cases
//only one element in array

if (start == end)
return arr[start];
//if two element
if (start + 1 == end) {
return max(arr[start], arr[end]);
}

int mid = start + (end - start) / 2;

//we got our peak
if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1])
return arr[mid];
//pivot element is still in the increasing part
else if (arr[mid] > arr[mid - 1] && arr[mid] < arr[mid + 1]) {
return findThePeakEfficientRecur(arr, mid + 1, end);
}
else
return findThePeakEfficientRecur(arr, start, mid - 1);
}

void findThePeakEfficient(vector<int>& arr)
{
cout << "..............Using efficient approach(binary search)......\n";

//O(logn) time complexity

int peakNumber = findThePeakEfficientRecur(arr, 0, arr.size() - 1);

if (peakNumber == -1)
cout << "There is no peak element in this array\n";
else
cout << "The peak element(maximum number) is " << peakNumber << "\n";

return;
}

int main()
{
cout << "Enter number of elements\n";
int n;
cin >> n;
vector<int> arr(n);
cout << "Enter the elements(increasing first &  then decreasing)\n";

for (int i = 0; i < n; i++)
cin >> arr[i];

//using navive approach
findThePeakNaive(arr);
//using binary search
findThePeakEfficient(arr);

return 0;
}
```

Output:

```Enter number of elements
6
Enter the elements(increasing first &  then decreasing)
3 10 17 15 2 -3
..............Using naive search......
The peak element(maximum number) is 17
..............Using efficient approach(binary search)......
The peak element(maximum number) is 17
```

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates