String Coding Problems

Arrays Coding Problems

Sorting Coding Problems

Searching Coding Problems

Coding Algorithms

Tree Coding Problems

Stack Coding Problems

Linked list Coding Problems

Graph Coding Problems

Greedy Algorithms Coding Problems

Dynamic Programming Coding Problems

Matrix Coding Problems

Recursion Coding Problems

Number Theory Coding Problems

Backtracking Coding Problems

Heap Coding Problems

Brute Force Coding Problems

Implementation Coding Problems

Google Contests

Competitive Programming Coding


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.


1 4 8 3 2



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.



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

FUNCTION findMaxBitonic (Input array, 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
    IF control comes out of the loop
        //for trivial cases like array size 1 or 2
        return array[array size-1]; 

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]<<" ";

//function to find the max
int findMaxBitonic(vector<int> a,int low,int 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
		if(a[mid]<a[mid-1] && a[mid+1]<a[mid]) //in decreasing zone
	return a[a.size()-1];

int main(){
	int n,item;

	cout<<"enter array size: ";

	vector<int> a;

	cout<<"input bitonic array of size: "<<n<<endl;
	for(int j=0;j<n;j++){
	cout<<"your bitonic array is:\n";
	cout<<"maximum in this bitonic array is:"<<findMaxBitonic(a,0,n-1)<<endl;
	return 0;


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.

Comments and Discussions!

Load comments ↻

Copyright © 2024 www.includehelp.com. All rights reserved.