Divide and conquer Binary Search

binary_search.py

def binary_search(A, low, high, k):
    """
    Search in a sorted array
    Args:
    A sorted array A[low...high]
    (∀low <= i < high: A[i] <= A[i+1]) monotonically decreasing

    Returns:
    An index, i, (low <= i <= high) where A[i] = k
    Otherwise the greatest index such that A[i] < k
    Otherwise (k < A[low]), the result is low
    
    Runtime: 
    T(n) = T(n/2) + c
    
    Problem size | Work
    n            | c
    n/2          | c
    n/4          | c
    .           
    .
    .
    1            | c
    0            | c
    
    Total: Sum(from 0 to log2n) c = Θ(log2n)
    """
    if high < low:
        return low - 1
    mid = low + (high - low) // 2
    if k == A[mid]:
        return mid
    elif k < A[mid]:
        return binary_search(A, low, mid - 1, k)
    else:
        return binary_search(A, mid + 1, high, k)
   
def binary_search_iterative(A, low, high, k):
    while low < high: 
        mid = low + (high - low) // 2
        if key == A[mid]:
            return mid
        elif k < A[mid]:
            high = mid - 1
        else: 
            low = mid + 1
    return low - 1