gistfile1.txt

def is_rotated(nums: List[int]) -> bool:
    first = nums[0]
    last = nums[-1]
    return first > last


def find_pivot(nums: List[int]) -> List[int]:
    def search_pivot(nums: List[int], last_index_pointer:int , index_pointer: int) -> int:
        cur = nums[index_pointer]
        low_side_of_cur = nums[index_pointer - 1]
        if cur < low_side_of_cur:
            return index_pointer
        print(index_pointer)
        if last_index_pointer < index_pointer:            
            lowside_index = last_index_pointer + int((index_pointer-last_index_pointer) / 2)
            highside_index = index_pointer + int((len(nums) - index_pointer)/2)

        if last_index_pointer > index_pointer:
            lowside_index = int(index_pointer / 2)
            highside_index = index_pointer + int(((len(nums) -last_index_pointer) - index_pointer)/2)

        highside_num = nums[highside_index]
        lowside_num = nums[lowside_index]
        if lowside_num > highside_num:
            return search_pivot(nums, index_pointer, highside_index)
        
        if lowside_num < highside_num:
            return search_pivot(nums, index_pointer, lowside_index)

    return search_pivot(nums,0, int(len(nums)/2))
      
def unrotate(nums: List[int], pivot_index:int) -> List[int]:
    return nums[pivot_index:] + nums[:pivot_index]


def search_sorted(nums: List[int], target: int) -> int:
    print("in search")
    def binary_search(nums: List[int], search_target:int, index_pointer: int) -> int:
        print(index_pointer)
        cur = nums[index_pointer]
        if cur == search_target:
            return index_pointer
        elif search_target > cur:
            new_index = int(index_pointer / 2)
        elif search_target < cur:
            new_index = index_pointer + int((len(nums) - index_pointer)/2)

        if new_index == index_pointer:
            return -1
        
        return binary_search(nums, search_target, new_index)

    return binary_search(nums, target, int(len(nums)/2))


def search(nums: List[int], target: int) -> int:
    roted = is_rotated(nums)
    if roted:
        pivot = find_pivot(nums)
        unrotated_nums = unrotate(nums, pivot)
        unrotated_index = search_sorted(unrotated_nums, target)
        print(f"uri: {unrotated_index}, p: {pivot}")
        if unrotated_index < pivot:
            return unrotated_index + pivot
        else:
            return unroated_index - pivot

    else:
        return search_sorted(nums, target)


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        search(nums, target)