class Solution:
  def search(self,arr, key):
    
    def binary_search(goleft):
      left, right = 0, len(arr) - 1

      while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == key:
          return mid
        elif goleft(key, arr[mid]):
          right = mid - 1
        else:
          left = mid + 1
      
      return -1
    

    is_ascending = arr[0] < arr[-1]

    if is_ascending:
      return binary_search(lambda key,mid: key < mid )
    else:
      return binary_search(lambda key,mid: key > mid )