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

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.

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);
}
cout<<"your bitonic array is:\n";
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
your bitonic array is:
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
your bitonic array is:
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.

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)

Time complexity: O(log(n))C++ implementationOutputExplanation with example:So, in this input case we only need one comparison, where if we had done in brute force, would have required 3 comparisons.

need an explanation for this answer? contact us directly to get an explanation for this answer