Local Minimum of an array

Problem: Given an array ‘a’ of N distinct integers, design an O(log N) algorithm to find a local minimum: an index i such that a[i-1] > a[i] < a[i+1].

Solution: If a[0] < a[1] or a[N - 2] > a[N - 1] then a[0] or a[N - 1] is the local minimum, respectively. Pick a[mid] where mid = N / 2. If it's not the answer, we have three cases:

   1)  If a[mid - 1] < a[mid] < a[mid + 1], lower half will contain the local minimum.

   2)  If a[mid - 1] > a[mid] > a[mid + 1], upper half will contain the local minimum.

   3)  If a[mid - 1] < a[mid] > a[mid + 1], either half will contain the local minimum.

Search on the new interval recursively.

Explanation:

If a[1] < a[2], a[1] is an LM.
Otherwise, if a[n-1] > a[n], a[n] is an LM.
Otherwise, the array entries start out descending (going from a[1] to a[2]) and ends up ascending (going from a[n-1] to a[n]).  It follows that an LM must exist somewhere in between.  Examine a[n/2].  If a[n/2] > a[n/2+1], then by the same reasoning there is an LM in the upper half of the array.  Similarly, if a[n/2] < a[n/2+1] there is an LM in the lower half of the array.  Solve recursively in the appropriate half.

public class LocalMinimum {

	public static int findLocalMinimum(int[] elements, int lowIndex, int highIndex) {
		if (lowIndex > highIndex) {
			return -1;
		}

		if (lowIndex == highIndex) {
			return lowIndex;
		}

		if (lowIndex + 1 == highIndex) {
			if (elements[lowIndex] < elements[highIndex]) {
				return lowIndex;
			}
			return highIndex;
		}

		int midIndex = (lowIndex + highIndex) / 2;

		if ((elements[midIndex] <= elements[midIndex - 1])
				&& (elements[midIndex] <= elements[midIndex + 1])) {
			return midIndex;
		}

		if (elements[midIndex] >= elements[midIndex + 1]) {
			return findLocalMinimum(elements, midIndex, highIndex);
		} else {
			return findLocalMinimum(elements, lowIndex, midIndex);
		}
	}
	
	public static void main(String[] args){
		int Arr[] = {8,5,4,3,1,2,6,9};
		int index = findLocalMinimum(Arr, 0, Arr.length-1);
		System.out.println("local mimimum is "+Arr[index]);
	}

}