Shifted array search - python

ShiftedArraySearch.py

def shifted_arr_search(shiftArr, num):
  
  def binary_search(arr, left, right, num):
    if right < left:
      return -1
    m = (left+ right) / 2
    if arr[m] == num:
      return m
    if arr[m] > num:
      return binary_search(arr, left, m - 1, num)
    else:
      return binary_search(arr, m + 1, right, num)
    
  def rec(left, right, arr, num):
    if left > right:
      return -1
    else:
      m = (left + right) / 2
      mid_number = shiftArr[m]
      if mid_number == num:
        return m
      
      
      if mid_number > shiftArr[left]:
        # shiftArr[l:m] is a sorted array
        # apply normal binary search if num is in this interval
        if num >= shiftArr[left] and num < mid_number:
          return binary_search(arr, left, m - 1, num)
      elif shiftArr[right] > mid_number:
        # shiftArry[m:right] is a sorted array
        # apply normal binary search if num is in this interval
        if num > mid_number and num <= shiftArr[right]:
          return binary_search(arr, m + 1, right, num)
        
        
      if mid_number > shiftArr[right]:
        # the pivot is in shiftARr[m:right]
        # if num is in this interval then i apply rec for this interval
        if num <= shiftArr[right]:
          return rec(m + 1, right, arr, num)
        
      elif shiftArr[left] > mid_number:
        # the pivot is in shiftArr[left:m]
        # if num is in this interval then I apply rec for this interval
        if num <= shiftArr[mid]:
          return rec(left, m - 1, arr, num)        
        
      return -1

  return rec(0, len(shiftArr) - 1, shiftArr, num)
  
shiftArr = [9, 12, 17, 2, 4, 5]
num = 6  
print shifted_arr_search(shiftArr, num)