Find Local Minimum in an unsorted array with unique elements

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/find-local-minima-in-a-given-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].

Examples:

a = [1,2,3,4,5] (increasing, increasing) a[0] is an LM
a = [5,4,3,2,1] (decreasing, decreasing) a[n] is an LM
a = [1,2,2,2,1] (increasing, decreasing) a[0] and a[n] are LMs

Solution:

Brute force 
Go through each element 3 tuples, and compare them.
Time complexity - O(n)

Solution 2
Can we do better? The answer is yes, we can do this in O(log n). Lets see how.

mid=(start+end)/2; 
1. If there is just one array element, it's a local minimum.
2. If there are two array elements, check each. One must be a local minimum.
3. Otherwise, look at the middle element of the array. 
   If it's a local minimum, return it. 
   Otherwise, at least one adjacent value must be smaller than this one. 
   Recurse in the half of the array containing that smaller element 
   (but not the middle).

Here is the code in java:

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]);
 }

}

Time complexity

T(1) ≤ 1
T(2) ≤ 1
T(n) ≤ T(n / 2) + 1

Using the Master Theorem, you can show that this algorithm runs in time O(log n), as required.

[Edit] - Note

1. We are not enumerating all the local minima in the array, but a single LM, which can be done in O(log n) time.
   The number of local minima can be n/2; you can't enumerate them all in O(log n) time.
   
2. It also doesn't guarantee whether we will get global minima or not. Consider the array
   {8,5,4,3,1,2,6,9}, the output will be 1, as it is only LM here, not because it is a global minima.
3. The method doesn't guarantee any particular local minima. Consider the array : {8,5,4,3,6,4,5,1,2,6,4,5,9}. The LM outputted by the code will be 3, which is one of the LMs in the array. The LMs we had in array were 3,4,1,4. But the code returned 3, which is one of the LMs. 

Reference
http://stackoverflow.com/questions/12238241/find-local-minima-in-an-array

Thanks