Find max element in unimodal array

In this case we’re going to find the max element in an unimodal array, so first things first and let’s define what an unimodal array is:

An unimodal array is one that has a sequence of increasing integers followed by a sequence of decreasing integers. All elements in the array must be unique.

For example:

increasingAndDecreasing = [2, 3, 4, 21, 43, 52, 51, 18, 11, 9, 6, 1]. Max value = 52.

The problem is that given an unimodal array we should find its maximum element.

In order to find a solution to this problem we can implement a variation of a binary search. Remember that a binary search is one divide and conquer algorithm that divides the array into two sub-arrays that may contain the search term. It discards one of the sub-array by utilising the fact that items are sorted. It continues halving the sub-arrays until it finds the search term or it narrows down the list to a single item. Definition taken from here.

Step by step solution:

1. Create a couple of variables to handle the left side index, and the right side index of the array, initially set them as left = 0, and right = n-1 (n is the array’s length).
2. Iterate while left < right.
3. Find the value that represents de array’s half (m).
4. Compare m against m+1, if the first one is lower than the second assign m+1 to left (meaning the biggest value is from m+1 to right). If the second value is bigger than the first one assign m to right (meaning the biggest value is from left to m).
5. Once the while is done return array[left] which is the maximum value in the array.

Java solution:

public static int find(final int[] array) {
  int left = 0;
  int right = array.length-1;
  int midPosition;

  while (left < right) {
    midPosition = (left + right) / 2;
    if (array[midPosition] < array[midPosition + 1]) {
      left = midPosition + 1; // the biggest element is from (midPosition + 1) to R
    } else if (array[midPosition] > array[midPosition + 1]) {
      right = midPosition; // the biggest element is from left to midPosition
    }
  }

  return array[left];
}

If we execute the previous code with next entrances:

int increasingAndDecreasing[] = {2, 3, 4, 21, 43, 52, 51, 18, 11, 9, 6, 1};
int increasing[] = {2, 3, 4, 21, 43, 52, 67, 101, 211};
int decreasing[] = {73, 52, 51, 18, 11, 9, 6, 1};

We get these results:

52
211
73

All the code can be found here.