# Search in Rotated Sorted Array

You are given an integer array nums sorted in ascending order (with distinct values), and an integer target.

Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

If target is found in the array return its index, otherwise, return -1.

**Example 1**

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

**Example 2**

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

**Example 3:**

Input: nums = [1], target = 0
Output: -1


1 if target < nums[mid]:
if nums[start] < nums[mid]:
end = mid
else:

def rotateSort(nums):
    start, end = 0, len(nums) - 1
    while start + 1 < end:
       mid = (start + end) // 2

       if nums[start] <= nums[mid]:
           if nums[start] <= target and target <= nums[mid]:
               end = mid
           else:
               start = mid
       else:
            if nums[mid] <= target and target <= nums[end]:
                start = mid
            else:
                end = mid
    
    if nums[start] == target:
        return start
    if nums[end] == target:
        return end
    return -1
               

---

Input
[4,5,6,7,8,1,2,3]
8
Output
-1
Expected
4

---
Wrong Answer
Runtime: 52 ms
Your input
[4,5,6,7,0,1,2]
0
[4,5,6,7,8,1,2,3]
8
stdout

Output
4
-1
Expected
4
4