# [Search In Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array/)
###### tags: `Leetcode`, `Medium`, `Binary Search`

## Approach

* The array is rotated if the leftmost number is greater than the rightmost number
* Find the mid element in the array. If the mid element is the target, then return the mid index
* If `nums[mid] >= nums[left]` then the mid element belongs to the left part of the array or the unrotated part of the array
* If `nums[left] <= target < nums[mid]` then check to the left of the array
* Otherwise check to the right of the array
* If `nums[mid] < nums[left]` then the mid element belongs to the right part of the array or the rotated part of the array
* If `nums[right] >= target > nums[mid]` then check to the right of the array
* Otherwise check to the left of the array
* Return -1

## Asymptotic Analysis
### Time Complexity: **O(log(N))**
### Space Complexity: **O(1)**

## Code

from typing import List


class SearchInRotatedSortedArray:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (right + left) // 2
            if target == nums[mid]:
                return mid

            if nums[mid] >= nums[left]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1


n, t = [4, 5, 6, 7, 0, 1, 2], 0
print("Searching for " + str(t) + " in " + str(n) + "\n" +
      "\tFound at index: " + str(SearchInRotatedSortedArray().search(n, t)))