# Find local minimum in an array
### Problem
Suppose we are given an array A[0:n] with the special property that A[0]>=A[1] and A[n-2]<=A[n-1]. We say that an element A[x] is a local minimum if it is less than or equal to both its neighbors, or more formally, if A[x-1]>=A[x] and A[x]<=A[x + 1]. Obviously the boundary element cannot be local minimum.

For example, there are six local minima in the following array:

We can obviously find a local minimum in O(n) time by scanning through the array. Describe and analyze an algorithm that finds a local minimum in O(log n) time. [Hint: With the given boundary conditions, the array must have at least one local minimum. Why?]

### Algorithm Description
We can take a binary search esque aproach and start at the middle of the array since there must be at least one local minimum, then cut into either left or right side of the array depending on circumstance.
Initial call to the fuction should have low = 1 and high = len(A) - 2

fun findLocalMin(A, low, high)
{
    if (len(A) < 3 or low > high)    return; // no local minimum in array
    
    var mid = (low + high) / 2;
    
    if (A[mid - 1] >= A[mid] and A[mid] <= A[mid + 1])    return A[mid];
    
    else if (A[mid] < A[mid - 1])    return findLocalMin(A, low, mid - 1);
    
    else return findLocalMin(A, mid + 1, high);
}

### Correctness proof
With the special properties given, from A[0] -> A[1] there is an decrease, from A[n-2] -> A[n-1] there is a increase. Therefore there must be a value in the array that lays between both boundaries, making it a local minimum.
Base case:
n < 3 or (low index > high index) -> no local minimum exists

Case 1:
n = 3 -> the singular local minimum is the middle value

Case 2:
( A[mid] < A[mid - 1] ) -> A local minimum must exist on the left half, algorithm recurses left half of array

Case 3:
( A[mid] > A[mid + 1] ) -> A local minimum must exist on the right half, algorithm recurses right half of array

There are no other cases. QED

### Time Complexity
Let T(n) be the time for an interval of length n. Each step does O(1) work and recurses on around half the range:
T(n) = *T*(n/2) + *O*(1) -> T(n) = *O*(log n)