Finding the maximum element in a bitonic array

Given an array in which the elements are increasing up to a point and then decreases (this is also called a bitonic array), how do we efficiently find the maximum element?

For example, the input arrays can look like {1, 3, 5, 4, 2} , {11, 17, 25, 36, 24, 6}.

Basically we need to find the point at which the elements start decreasing. It can be anywhere in the array.

The obvious linear search for maximum takes O(n) time. But we can utilize the sorted property of two parts of the arrays to solve it in O(log n).

Here is how the algorithm works.

Go to the middle element and check if it is greater than both the left and right elements. If it is, then we found the maximum element.

Eg: {1, 3, 5, 4, 2}

If the left element is greater than the middle element, we can ignore the right half and search only in left half.

Eg: {1, 5, 4, 3, 2}

If the right element is greater than the middle element, we can ignore the left half and search only in right half.

Eg: {1, 5, 7, 9, 3}

We need to handle the cases where the middle element falls on the boundaries of the array. This happens when the entire array is sorted either in ascending order or descending order. Eg: {1, 2, 3, 4, 5} or {5, 4, 3, 2, 1}

If the right part is empty, and the middle element is greater than left element, we can eliminate the left part.
Similarly if the left part is empty, and the middle element is greater than right element, we can eliminate the right part.

Test cases:

{1, 3, 5, 4, 2}
{1, 2, 3, 4, 5}
{5, 4, 3, 2, 1}
{1}
{1, 2, 2, 4, 5, 3}
{10, 20}

Here is the iterative C++ implementation of the above algorithm.

	#include <iostream>
	#include <vector>

	using namespace std;

	//Find max element in an array which contains elements
	//First in ascending and then descending order
	int find_max_asc_desc(vector<int> & arr)
	{
	int sz = arr.size();
	int low = 0, high = sz-1;
	int mid;
	while( low < high )
	{
	mid = low + (high-low)/2;

	//If previous and next elements are not crossing the boundary
	if( mid-1 >= 0 && mid+1 < sz )
	{
	//return the middle element if the middle element is greater than its neighbors
	if( arr[mid] > arr[mid-1] && arr[mid] > arr[mid+1] )
	{
	return arr[mid];
	}
	else if( arr[mid-1] > arr[mid] ) //search lower half
	{
	high = mid-1;
	}
	else //search upper half
	{
	low = mid+1;
	}
	}
	else if( mid-1 >= 0 ) // we reached the right end
	{
	if( arr[mid] > arr[mid-1] )
	low = mid;
	else
	high = mid-1;
	}
	else //we reached the left end
	{
	if( arr[mid] > arr[mid+1] )
	high = mid;
	else
	low = mid+1;
	}
	}
	return arr[low]; //low and high are equal; we can return arr[high] also
	}

	void Test()
	{
	vector<int> nums;
	nums.push_back(1);
	nums.push_back(3);
	nums.push_back(5);
	nums.push_back(4);
	nums.push_back(2);
	cout << find_max_asc_desc(nums) << endl;
	}
	int main()
	{
	Test();
	return 0;
	}

view raw max_bitonic.cpp hosted with

by GitHub

Leave a Reply Cancel reply