# Maximum value in a bitonic array

In this article, we are going to see how to find the maximum value in a bitonic array in optimized time complexity? This problem has been featured in interview coding round of Amazon.
Submitted by Radib Kar, on January 30, 2019

Problem statement:

Given a bitonic array find the maximum value of the array. An array is said to be bitonic if it has an increasing sequence of integers followed immediately by a decreasing sequence of integers.

Example:

```Input:
1 4 8 3 2

Output:
8
```

Solution:

Definitely the brute force solution even works in linear time where you just pick each element and compare with the previous & next element. That’s pretty simple. But the concept of bitonic search leads up to more optimized solution reducing the number of comparison.

Algorithm:

Pre-requisite:

Bitonic array, low index (lower bound), high index (upper bound)

```FUNCTION findMaxBitonic (Input array, low, high){
While(low<=high){
1.	Set mid to (low+high)/2;
2.	Comparisons
IF(array [mid]>array[mid-1] &&array[mid]>array[mid+1])
Return array[mid]; //as this is the maximum
//in the increasing region of the bitonic array
IF(array[mid]>array[mid-1] &&array[mid]<array[mid+1])
low=mid+1; //move lower bound up
//in the decreasing region of the bitonic array
ELSE IF(array[mid]<array[mid-1] &&array[mid+1]<array[mid])
high=mid-1; //move upper bound down
END WHILE
IF control comes out of the loop
//for trivial cases like array size 1 or 2
return array[array size-1];
END FUNCTION
```

Time complexity: O(log(n))

C++ implementation

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

//printing the array
void print(vector<int> a,int n){
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
}

//function to find the max
int findMaxBitonic(vector<int> a,int low,int high){
while(low<=high){
int mid=(low+high)/2;

if(a[mid]>a[mid-1] && a[mid]>a[mid+1]) //the maximum
return a[mid];
if(a[mid]>a[mid-1] && a[mid]<a[mid+1]) //in increasing zone
low=mid+1;
if(a[mid]<a[mid-1] && a[mid+1]<a[mid]) //in decreasing zone
high=mid-1;
}
return a[a.size()-1];
}

int main(){
int n,item;

cout<<"enter array size: ";
scanf("%d",&n);

vector<int> a;

cout<<"input bitonic array of size: "<<n<<endl;
for(int j=0;j<n;j++){
scanf("%d",&item);
a.push_back(item);
}
print(a,n);
cout<<"maximum in this bitonic array is:"<<findMaxBitonic(a,0,n-1)<<endl;

return 0;
}
```

Output

```First run:
enter array size: 5
input bitonic array of size: 5
1 4 8 3 2
1 4 8 3 2
maximum in this bitonic array is:8

Second run:
enter array size: 10
input bitonic array of size: 10
6 8 20 12 11 9 7 5 0 -4
6 8 20 12 11 9 7 5 0 -4
maximum in this bitonic array is:20
```

Explanation with example:

```Input array, arr:
1 4 8 3 2
Array size: 5

In the main function we call findMaxBitonic (arr, 0, 4);
Input array = arr
low = 0
high = 4
-----------------------------------------------------------

findMaxBitonic (arr, 0, 4)
0th iteration
low<high (0<4)
mid= (low +high)/2 = 2
arr[mid]>arr[mid+1] && arr[mid]>arr[mid-1] // 8>4 && 8>3
return arr[mid] //return 8
maximum in the bitonic array=8
```

So, in this input case we only need one comparison, where if we had done in brute force, would have required 3 comparisons.

What's New

Top Interview Coding Problems/Challenges!

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