# Find Local Minimum in an Array
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
The following algorithm uses a binary search approach to find the local minimum. The function findLM() looks at the middle element of the array and continues to cut it in half and examine each middle element until a local minimum is found (both sides of the element are larger or equal to it).

fun findLM(A, low, high){

    //element must have 2 neighbors
    var size = len(A);
    if(A < 3) return -1;

    //single element
    if(low == high) return low;
    
    //find middle element
    var middle = (low + high) / 2;
    
    //checks for local min
    if(A[middle - 1] >= A[middle] and A[middle] <= A[middle + 1]){
        return middle;
    }
    
    //check left side
    if(A[middle - 1] < A[middle]){
        return findLM(A, low, middle - 1);
    }
    //check right side
    else{
        return findLM(A, middle + 1, high);
    }
}

fun localMin(A){
    return findLM(A, 1, len(A) - 2);
}

//sample call
var A = [9, 7, 7, 2, 1, 3];
var index = localMin(A);
print A[index];

# Correctness Proof
**Goal:** The function findLM(A, low, high) correctly finds and returns the index of a local minimum in an array A given the following conditions:
* A[0] >= A[1]
* A[n-2] <= A[n-1]

**Base Cases:**
* n = 1: If there is one element in the array, the function returns -1 since it has no neighbors.
* n = 2: If there are two elements in the array, the function returns -1 since an element must have two neighbors to be a local minimum

**Induction Hypothesis:**
Assume for any subarray size smaller than n, the function findLM correctly finds and returns the index of a local minimum.

Let middle = (low + high) / 2
1. If A[middle - 1] >= A[middle] and A[middle] <= A[middle + 1], A[middle] is a local element and the function returns its index.
2. If A[middle - 1] < A[middle], the array is decreasing on the left side. The function findLM(A, low, middle - 1) is called and finds a local minimum in the left half.
3. If A[middle + 1] < A[middle], the array is decreasing on the right side. The function findLM(A, middle + 1, high) is called and finds a local minimum in the right half.

There are no other cases. QED.
# Time Complexity
Let T(n) denote the time complexity of a subarray of size n.
* finding the middle of the array -> O(n)
* one recursive call is made on a subarray of size n/2 (at most)

T(n) = T(n/2)+ O(1)
T(n) = O(logn)