# Problem:
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]

# algorithm descripition
My algorithm works by finding the middle (m) and comparing it to the left and right values. If the left value is smaller, than the algorithm discards the right side of the array (hi). If the right value is smaller, then the algorithm discards the left side of the array (lo). Then the function repeats until it finds a Local Minimum (lo).

def local_min(A):
    n = len(A)
    
    def search(lo,hi):
        if lo == hi:
            return lo
    
        m = (lo + hi) // 2
        
        if A[m - 1] >= A[m] <= A[m + 1]:   
            return m
        elif A[m - 1] < A[m]:
            return search (lo, m - 1)
        else:
            return search(m + 1, hi)
    return search(1,n - 2)

# correctness proof
Goal: This function should return lo, which is the local minimum of any give array with the same restrictions. This function should also be within O(log n) time.

**Base Case** (L = 1)
if lo == hi, then it returns lo
**Inductive Step**
Case 1: A[m - 1] >= A[m] <= A[m + 1]
If A[m] is smaller than both the left and right, return m as a local minimum.
Case 2: A[m - 1] < A[m]
if A[m] is larger than the left value, there must be a value on the left that contains a local minimum, so we discard the right.
Case 3: A[m] > A[m + 1]
if A[m] is larger than the right value, there must be a value on the right that contains a local minimum, so we discard the left.

There are no other cases. QED.

# time complexity
Each recursive step discards at least half of the interval, which makes the time complexity solve into O(log n) since O is constant work.