element_in_sort_rotate.py

def search(nums,target):
    start = 0
    end = len(nums) - 1
    half_end = 0

    while start <= end:
        mid = start + (end - start) // 2

        # nodes
        next_node = (mid + 1) % len(nums)
        prev_node = (mid + len(nums) - 1) % len(nums)

        if nums[mid] <= nums[next_node] and nums[mid] <= nums[prev_node]:
            half_end = mid
            break
        elif nums[mid] <= nums[end]:
            end = mid - 1
        else:
            start = mid + 1
    
    # left half
    start = 0
    end = half_end - 1
    left = -1

    while start <= end:
        mid = start + (end - start) // 2

        if target == nums[mid]:
            left = mid
            break
        elif target < nums[mid]:
            end = mid - 1
        else:
            start = mid + 1

    # right half
    start = half_end
    end = len(nums) - 1
    right = -1

    while start <= end:
        mid = start + (end - start) // 2

        if target == nums[mid]:
            right = mid
            break
        elif target < nums[mid]:
            end = mid - 1
        else:
            start = mid + 1

    if left == -1:
        return right
    elif right == -1:
        return left
    else:
        return 0