# Leetcode 33 - Search in rotated sorted array

`Note:`

- Update
- Don’t just compare
`nums[middle]`

with`target`

because`target`

can be on either side. - Compare
`nums[middle]`

with`nums[left]`

first to check which situation we’re talk about.

- Don’t just compare
- Because of the time complexity requirement, we can know we must use
`binary search`

- The direction of moving
`left, right`

pointers depends on where the pivot is, there are two situations:- We can check the pos of pivot by comparing
`left`

with`middle`

.

- We can check the pos of pivot by comparing
- Only by checking
`nums[middle] > target`

is not enough.- For example:
- Both of these two pos of target meet
`nums[m] > target`

. - We need to compare
`target`

with`left/right`

as well.

`Question:`

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:`

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

`Code:`

1 | /** |