Welcome to Subscribe On Youtube
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)$.
-
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; } }