# 33. Search in Rotated Sorted Array

## Description

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


Constraints:

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• All values of nums are unique.
• nums is an ascending array that is possibly rotated.
• -104 <= target <= 104

## Solutions

Solution 1: Binary Search

We use binary search to divide the array into two parts, $[left,.. mid]$ and $[mid + 1,.. right]$. At this point, we can find that one part must be sorted.

Therefore, we can determine whether $target$ is in this part based on the sorted part:

• If the elements in the range $[0,.. mid]$ form a sorted array:
• If $nums[0] \leq target \leq nums[mid]$, then our search range can be narrowed down to $[left,.. mid]$;
• Otherwise, search in $[mid + 1,.. right]$;
• If the elements in the range $[mid + 1, n - 1]$ form a sorted array:
• If $nums[mid] \lt target \leq nums[n - 1]$, then our search range can be narrowed down to $[mid + 1,.. right]$;
• Otherwise, search in $[left,.. mid]$.

The termination condition for binary search is $left \geq right$. If at the end we find that $nums[left]$ is not equal to $target$, it means that there is no element with a value of $target$ in the array, and we return $-1$. Otherwise, we return the index $left$.

The time complexity is $O(\log n)$, where $n$ is the length of the array $nums$. The space complexity is $O(1)$.

• class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
int left = 0, right = n - 1;
while (left < right) {
int mid = (left + right) >> 1;
if (nums[0] <= nums[mid]) {
if (nums[0] <= target && target <= nums[mid]) {
right = mid;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[n - 1]) {
left = mid + 1;
} else {
right = mid;
}
}
}
return nums[left] == target ? left : -1;
}
}

• class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
int left = 0, right = n - 1;
while (left < right) {
int mid = (left + right) >> 1;
if (nums[0] <= nums[mid]) {
if (nums[0] <= target && target <= nums[mid])
right = mid;
else
left = mid + 1;
} else {
if (nums[mid] < target && target <= nums[n - 1])
left = mid + 1;
else
right = mid;
}
}
return nums[left] == target ? left : -1;
}
};

• # below 2 solutions, diff is while condition: left ('<' or '<=') right

# I like this better
class Solution:
def search(self, nums: List[int], target: int) -> int:
n = len(nums)
left, right = 0, n - 1
while left <= right:
mid = (left + right) >> 1
if nums[mid] == target:
return mid
elif nums[0] <= nums[mid]: # left half sorted
if nums[0] <= target <= nums[mid]:
right = mid - 1
else:
left = mid + 1
else: # right half sorted
if nums[mid] < target <= nums[n - 1]:
left = mid + 1
else:
right = mid -1
return -1

############

class Solution:
def search(self, nums: List[int], target: int) -> int:
n = len(nums)
left, right = 0, n - 1
while left < right:
mid = (left + right) >> 1
if nums[0] <= nums[mid]: # left half sorted
if nums[0] <= target <= nums[mid]:
right = mid
else:
left = mid + 1
else: # right half sorted
if nums[mid] < target <= nums[n - 1]:
left = mid + 1
else:
right = mid
return left if nums[left] == target else -1


• func search(nums []int, target int) int {
n := len(nums)
left, right := 0, n-1
for left < right {
mid := (left + right) >> 1
if nums[0] <= nums[mid] {
if nums[0] <= target && target <= nums[mid] {
right = mid
} else {
left = mid + 1
}
} else {
if nums[mid] < target && target <= nums[n-1] {
left = mid + 1
} else {
right = mid
}
}
}
if nums[left] == target {
return left
}
return -1
}

• function search(nums: number[], target: number): number {
const n = nums.length;
let left = 0,
right = n - 1;
while (left < right) {
const mid = (left + right) >> 1;
if (nums[0] <= nums[mid]) {
if (nums[0] <= target && target <= nums[mid]) {
right = mid;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[n - 1]) {
left = mid + 1;
} else {
right = mid;
}
}
}
return nums[left] == target ? left : -1;
}


• /**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function (nums, target) {
const n = nums.length;
let left = 0,
right = n - 1;
while (left < right) {
const mid = (left + right) >> 1;
if (nums[0] <= nums[mid]) {
if (nums[0] <= target && target <= nums[mid]) {
right = mid;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[n - 1]) {
left = mid + 1;
} else {
right = mid;
}
}
}
return nums[left] == target ? left : -1;
};


• impl Solution {
pub fn search(nums: Vec<i32>, target: i32) -> i32 {
let mut l = 0;
let mut r = nums.len() - 1;
while l <= r {
let mid = (l + r) >> 1;
if nums[mid] == target {
return mid as i32;
}

if nums[l] <= nums[mid] {
if target < nums[mid] && target >= nums[l] {
r = mid - 1;
} else {
l = mid + 1;
}
} else {
if target > nums[mid] && target <= nums[r] {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
-1
}
}


• class Solution {
/**
* @param integer[] $nums * @param integer$target
* @return integer
*/

function search($nums,$target) {
$foundKey = -1; foreach ($nums as $key =>$value) {
if ($value ===$target) {
$foundKey =$key;
}
}
return \$foundKey;
}
}