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
numsare unique. numsis 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)$.
Python3
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]:
if nums[0] <= target <= nums[mid]:
right = mid
else:
left = mid + 1
else:
if nums[mid] < target <= nums[n - 1]:
left = mid + 1
else:
right = mid
return left if nums[left] == target else -1
Java
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;
}
}
C++
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;
}
};
Go
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
}
TypeScript
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;
}
Rust
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
}
}
JavaScript
/**
* @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;
};
C#
public 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;
}
}
PHP
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;
}
}