def binary_search(arr, target):
    """
    arr must be sorted, O(nlogn)
    given an array and a target value, return the index
    returns -1 if the target is not present

    Best case: O(1)
    Worst case: O(log n)
    Worst case space: O(1)
    """
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if target > arr[mid]:
            low = mid + 1
        elif target < arr[mid]:
            high = mid - 1
        else:
            return mid
    return -1

    # replace with this line for nearest
    # return low if arr[low] - target < target - arr[high] else high