Search in Rotated Sorted Array
Problem Statement
You are given an array of length n
which was originally sorted in ascending order. It has now been rotated between 1
and n
times. For example, the array nums = [1,2,3,4,5,6]
might become:
[3,4,5,6,1,2]
if it was rotated4
times.[1,2,3,4,5,6]
if it was rotated6
times.
Given the rotated sorted array nums
and an integer target
, return the index of target
within nums
, or -1
if it is not present.
You may assume all elements in the sorted rotated array nums
are unique,
A solution that runs in O(n)
time is trivial, can you write an algorithm that runs in O(log n) time
?
Example 1:
Input: nums = [3,4,5,6,1,2], target = 1
Output: 4
Example 2:
Input: nums = [3,5,6,0,1,2], target = 4
Output: -1
Constraints:
1 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-1000 <= target <= 1000
You should aim for a solution with O(log n)
time and O(1)
space, where n
is the size of the input array.
Recommended Time and Space Complexity
You should aim for a solution with O(log n)
time and O(1)
space, where n
is the size of the input array.
Hint 1
A brute force solution would be to do a linear search on the array to find the target element. This would be an O(n)
solution. Can you think of a better way? Maybe an efficient searching algorithm is helpful.
Hint 2
Given that the array is rotated after sorting, elements from the right end are moved to the left end one by one, creating two sorted segments separated by a deflection point due to the rotation. For example, consider the array [3, 4, 1, 2]
, which is rotated twice, resulting in two sorted segments: [3, 4]
and [1, 2]
. In a fully sorted array, it’s easy to find the target. So, if you can identify the deflection point (cut), you can perform a binary search on both segments to find the target element. Can you use binary search to find this cut?
Hint 3
We perform a binary search on the array with pointers l
and r
, which belong to two different sorted segments. For example, in [3, 4, 5, 6, 1, 2, 3]
, l = 0
, r = 6
, and mid = 3
. At least two of l
, mid
, and r
will always be in the same sorted segment. Can you find conditions to eliminate one half and continue the binary search? Perhaps analyzing all possible conditions for l
, mid
, and r
may help.
Hint 4
There are two cases: l
and mid
belong to the left sorted segment, or mid
and r
belong to the right sorted segment.
If l
and mid
are in the same segment, nums[l] < nums[mid]
, so the pivot index must lie in the right part. If mid
and r
are in the same segment, nums[mid] < nums[r]
, so the pivot index must lie in the left part. After the binary search, we eventually find the pivot index. Once the pivot is found, it’s straightforward to select the segment where the target lies and perform a binary search on that segement to find its position. If we don’t find the target, we return -1
.
Solution
Brute Force
def search(nums: List[int], target: int) -> int: for i in range(len(nums)): if nums[i] == target: return i return -1
Time complexity: O(n)
Space complexity: O(1)
Binary Search
def search(nums: List[int], target: int) -> int: left, right = 0, len(nums) - 1
while left < right: mid = (left + right) // 2 if nums[mid] > nums[right]: left = mid + 1 else: right = mid
pivot = left
def binary_search(left_bound: int, right_bound: int) -> int: while left_bound <= right_bound: mid = (left_bound + right_bound) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left_bound = mid + 1 else: right_bound = mid - 1 return -1
result = binary_search(0, pivot - 1) if result != -1: return result
return binary_search(pivot, len(nums) - 1)
Time complexity: O(log n)
Space complexity: O(1)
Binary Search (Two Pass)
def search(nums: List[int], target: int) -> int: left, right = 0, len(nums) - 1
while left < right: mid = (left + right) // 2 if nums[mid] > nums[right]: left = mid + 1 else: right = mid
pivot = left left, right = 0, len(nums) - 1
if target >= nums[pivot] and target <= nums[right]: left = pivot else: right = pivot - 1
while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1
return -1
Time complexity: O(log n)
Space complexity: O(1)
Binary Search (One Pass)
def search(nums: List[int], target: int) -> int: left, right = 0, len(nums) - 1
while left <= right: mid = (left + right) // 2 if target == nums[mid]: return mid
if nums[left] <= nums[mid]: if target > nums[mid] or target < nums[left]: left = mid + 1 else: right = mid - 1
else: if target < nums[mid] or target > nums[right]: right = mid - 1 else: left = mid + 1 return -1
Time complexity: O(log n)
Space complexity: O(1)