Question

A sequence of integers x1,x2,...,xn is unimodal if for some 1 ≤ i ≤ n we have x1 < x2 < ... < xi and xi > xi+1 > ... > xn. Find the maximum element in a unimodal sequence of integers x1, x2, . . . , xn. The running time should be O(log n). Show that your algorithm meets the bound.

Answer 1

Maximum element in a unimodal sequence of integers x1<x2<......xi-1<xi>xi+1>...xn can be achieved through binary search with O(log n) time complexity

with mid element greater than adjacent elements then mid is the maximum.

In the diagram below you could see maximum can be found while iterating to right side of the tree. We do not require to iterate through each element. Hence it's complexity can be found with general O(log n) time complexity.

Below diagram there is code snippet, where you can also cross-check that you do not need to iterate through every element unless it is the worst case i.e. elements in an array in ascending order but that's not unimodal sequence. So it has time complexity of O(log n) for every case :)


Code Snippet
static int findMaxUnimodal(int arr[], int low, int high){

       if (low == high) //single element array condition
return arr[low];

       if ((high == low + 1) && arr[low] >= arr[high]) //two element scenario
return arr[low];

       if ((high == low + 1) && arr[low] < arr[high])
  return arr[high];

       int mid = (low + high)/2;   

       if ( arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1])
  return arr[mid];

       if (arr[mid] > arr[mid + 1] && arr[mid] < arr[mid - 1])
  return findMaxUnimodal(arr, low, mid-1);

       else
  return findMaxUnimodal(arr, mid + 1, high);

    }