Search in Rotated Sorted Array
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.
Constraints:
- 1 <= nums.length <= 5000
- -10^4 <= nums[i] <= 10^4
- All values of nums are unique
- nums is an ascending array that is possibly rotated
- -10^4 <= target <= 10^4
Input Format:
- nums: An integer array sorted in ascending order and possibly rotated
- target: An integer to search for in the array
Output Format:
- An integer representing the index of target in nums, or -1 if target is not in nums
Examples:
Example 1:
Input:
nums = [4,5,6,7,0,1,2], target = 0
Output:
4
Explanation:
Target 0 is found at index 4
Example 2:
Input:
nums = [4,5,6,7,0,1,2], target = 3
Output:
-1
Explanation:
Target 3 is not in the array, so return -1
Example 3:
Input:
nums = [1], target = 0
Output:
-1
Explanation:
Target 0 is not in the array, so return -1
Solutions
Modified Binary Search
Identify which half of the array is sorted and check if the target is in that half. If not, search the other half.
Find Pivot Then Binary Search
First find the pivot point (the smallest element) in the rotated array, then perform a normal binary search in the appropriate half.
Algorithm Walkthrough
Example input: nums = [4,5,6,7,0,1,2], target = 0
Step-by-step execution:
- Input: nums = [4,5,6,7,0,1,2], target = 0
- Initialize left = 0, right = 6
- Iteration 1:
- mid = 3, nums[mid] = 7
- nums[mid] (7) != target (0)
- nums[left] (4) <= nums[mid] (7), so left side is sorted
- target (0) is not in range [4, 7), search the right half
- left = mid + 1 = 4
- Iteration 2:
- left = 4, right = 6, mid = 5, nums[mid] = 1
- nums[mid] (1) != target (0)
- nums[left] (0) <= nums[mid] (1), so left side is sorted
- target (0) is in range [0, 1), search the left half
- right = mid - 1 = 4
- Iteration 3:
- left = 4, right = 4, mid = 4, nums[mid] = 0
- nums[mid] (0) == target (0), return mid = 4
Hints
Hint 1
Hint 2
Hint 3
Hint 4
Video Tutorial
Video tutorials can be a great way to understand algorithms visually
Visualization
Visualize the binary search process in a rotated array, showing how we determine which half to search in each step.
Key visualization elements:
- current mid point
- sorted half
- rotated half
- search region
Implementation Notes
This problem combines binary search with the concept of a rotated array. The key insight is identifying which half of the array is sorted, and then determining if the target is in the sorted half.