class Solution:
  def search(self, arr, key):
    # standard binary search 
    def binary_search(b, e):
      while b <= e:
        m = (b + e) // 2
        if arr[m] == key:
          return m 
        elif arr[m] < key:
          b = m + 1
        else:
          e = m - 1
      return -1

    '''
      original array 
      1 2 3 4 5 6 7 8 9 10 11 12

      case: 1 b < m > e
      4 5 6 7 8 9 10 11 12 1 2 3
      ^           ^            ^
      b           m            e
      if key in the sorted range 
          do binary search 
      else:
          discard the sorted side
          
      case 2:  b > m < e
      10 11 12 1 2 3 4 5 6 7 8 9
      ^          ^             ^
      b          m             e
      if key in the sorted range 
          do binary search 
      else:
          discard the sorted side

      case 3, 4
      1 2 3 4 5 6 7 8 9 10 11 12
      12 11 10 9 8 7 6 5 4 3 2 1
      '''

    b, e = 0, len(arr) - 1
    while b <= e:
      m = (b + e) // 2
      # case 1: detect rotation in the second half
      if arr[b] <= arr[m] and arr[m] >= e:
        if key >= arr[b] and key <= arr[m]:
          return binary_search(b, m)
        else:
          b = m + 1
      # case 2: detect rotation in the first half
      elif arr[b] >= arr[m] and arr[m] <= e:
        if key >= arr[m] and key <= arr[e]:
          return binary_search(m, e)
        else:
          e = m - 1
      # case 3: no rotation at all
      # case 4: rotated on the last element = full sorted in descending order 
      elif (arr[b] <= arr[m] and arr[m] <= e) or (arr[b] >= arr[m] and arr[m] >= e):
        return binary_search(b, e)
        
    return -1