Binary Search Rotated Sorted Array.py

#assume no duplicates in array
def searchRotatedArray(arr, target):
  #runtime - O(lgN)
  #space - O(1)
  lo = 0
  hi = len(arr) - 1
  while(lo <= hi):
    mid = (lo + hi)//2
    #if we find the element then we are done
    if arr[mid] == target:
      return mid
    #case 1 arr[lo] > arr[mid] -> we have pivot in between
    if arr[lo] > arr[mid]:
      if target >= arr[lo] or target <= arr[mid]:
        hi = mid - 1
      else:
        lo = mid + 1

    #pivot is not within arr[lo] - arr[mid]
    else:
      #case 2 arr[lo] < arr[mid] -> no pivot, so if target is within arr[lo] and arr[mid]
      #then we just perform normal binary search
      #if target is not within arr[lo] <= target < arr[mid] then if it exists its in upper half
      if arr[lo] <= target < arr[mid]:
        hi = mid - 1
      else:
        lo = mid + 1
  return -1