def ternary_search(left, right, key, arr):
    """
    Find the given value (key) in an array sorted in ascending order.
    Returns the index of the value if found, and -1 otherwise.
    If the index is not in the range left..right (ie. left <= index < right) returns -1.
    """

    while right >= left:
        mid1 = left + (right-left) // 3
        mid2 = right - (right-left) // 3

        if key == arr[mid1]:
            return mid1
        if key == mid2:
            return mid2

        if key < arr[mid1]:
            # key lies between l and mid1
            right = mid1 - 1
        elif key > arr[mid2]:
            # key lies between mid2 and r
            left = mid2 + 1
        else:
            # key lies between mid1 and mid2
            left = mid1 + 1
            right = mid2 - 1

    # key not found
    return -1