# 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.
• 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.
• 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, nums, ..., 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:

Code: