from typing import List


def find(arr: List[int], key: int) -> int:
    """Modified version of binary search: one half of the array must be already sorted.
    Therefore check the sorted half to decide whether to search the left or right half.
    This takes O(lg n) time and O(1) space.
    """
    lo = 0
    hi = len(arr) - 1
    while lo <= hi:
        mid = int(lo / 2 + hi / 2)
        if key == arr[mid]:
            return mid
        # left partition is sorted
        if arr[lo] <= arr[mid]:
            if arr[lo] <= key < arr[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:  # right partition is sorted
            if arr[mid] < key <= arr[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1