> For the complete documentation index, see [llms.txt](https://www.vjssn.dev/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://www.vjssn.dev/practice/24-06-29/lc033-search-in-rotated-sorted-array.md).

# LC033 - Search in Rotated Sorted Array

## Problem

There is an integer array `nums` sorted in ascending order (with **distinct** values).

Prior to being passed to your function, `nums` is **possibly rotated** at an unknown pivot index `k` (`1 <= k < nums.length`) such that the resulting array is `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]` (**0-indexed**). For example, `[0,1,2,4,5,6,7]` might be rotated at pivot index `3` and become `[4,5,6,7,0,1,2]`.

Given the array `nums` **after** the possible rotation and an integer `target`, return *the index of* `target` *if it is in* `nums`*, or* `-1` *if it is not in* `nums`.

You must write an algorithm with `O(log n)` runtime complexity.

### Example

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

**Output:** 4

## Solution

Do a binary search. Time complexity is $$O(\log n)$$, no extra space used.

```python
def search(self, nums: List[int], target: int) -> int:
	left = 0
	right = len(nums) - 1

	while left <= right:
		mid = (left + right) // 2
		if target == nums[mid]:
			return mid

	# left section
	if nums[left] <= nums[mid]:
		if target > nums[mid] or target < nums[left]:
			left = mid + 1
		else:
		# search left
			right = mid - 1

	# right section
	else:
		if target < nums[mid] or target > nums[right]:
			right = mid - 1
		else:
		# search right
			left = mid + 1
	
	# if not found
	return -1
```