🟨 Search in Rotated Sorted Array (#33)
🔗 Problem Link
📋 Problem Statement
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.
💡 Examples
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
🔑 Key Insights & Approach
Core Observation: At least one half of the array is always sorted. Determine which half is sorted, then check if target is in that sorted half.
Why Modified Binary Search?
- O(log n) time complexity required
- One half is always sorted after rotation
- Can determine which half to search based on sorting
Approaches:
- Find pivot then binary search: O(log n)
- Single pass binary search with sorted half detection: O(log n) - optimal
Pattern: "Modified Binary Search" for rotated arrays with target search.
🐍 Solution: Python
Approach: Single Pass Binary Search
Time Complexity: O(log n) | Space Complexity: O(1)
from typing import List
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
# Determine which half is sorted
if nums[left] <= nums[mid]:
# Left half is sorted
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
# Right half is sorted
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
Approach 2: With Detailed Comments
Time Complexity: O(log n) | Space Complexity: O(1)
from typing import List
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
# Found target
if nums[mid] == target:
return mid
# Check if left half is sorted
if nums[left] <= nums[mid]:
# Left half [left...mid] is sorted
# Check if target is in this sorted portion
if nums[left] <= target < nums[mid]:
right = mid - 1 # Search left half
else:
left = mid + 1 # Search right half
else:
# Right half [mid...right] is sorted
# Check if target is in this sorted portion
if nums[mid] < target <= nums[right]:
left = mid + 1 # Search right half
else:
right = mid - 1 # Search left half
return -1
🔵 Solution: Golang
Approach: Binary Search
Time Complexity: O(log n) | Space Complexity: O(1)
func search(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
if nums[mid] == target {
return mid
}
// Check which half is sorted
if nums[left] <= nums[mid] {
// Left half is sorted
if nums[left] <= target && target < nums[mid] {
right = mid - 1
} else {
left = mid + 1
}
} else {
// Right half is sorted
if nums[mid] < target && target <= nums[right] {
left = mid + 1
} else {
right = mid - 1
}
}
}
return -1
}