You have given an array in which numbers are first increasing and then decreasing. Find the maximum element in O(log n).

An integer array with unique elements has the following property – elements initially are in increasing order till a point after which they start to decrease. Implement a function to find the index of the maximum element in the array in less than linear time, i.e., O(n).

Example:
Input: array = {1, 3, 5, 7, 9, 8, 6, 4} Output: max index = 4

	public class Array1 {
	public int fun(int arr[], int low, int high) {
	int index = -1;
	if (low < high) {
	int mid = low + ((high - low) / 2);
	if (arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1]) {
	index = mid;
	return index;
	}
	if (arr[mid] > arr[mid - 1]) {
	return fun(arr, mid, high);
	}
	if (arr[mid] > arr[mid + 1]) {
	return fun(arr, low, mid);
	}
	}
	return index;
	}
	public static void main(String[] args) {
	// TODO Auto-generated method stub
	int arr[] = { 1, 3, 5, 7, 9, 8, 6, 4 };
	int arr2[] = null;
	Array1 a = new Array1();
	int maxIndex = a.fun(arr, 0, arr.length - 1);
	System.out.println("Max Index : " + maxIndex
	+ ". Max Element value is : " + arr[maxIndex]);
	}
	}

view raw gistfile1.txt hosted with ❤ by GitHub

Max Index : 4.  Max Element value is : 9