Search in Rotated Sorted Array
Task example: Search in Rotated Sorted Array
A non-empty array nums contains distinct integers in increasing order, possibly rotated. Given target, return its index, or -1 if it is absent. Keep nums unchanged. The required runtime is O(log n); the linear scan below is a baseline.
Target 0 is at index 4, so return 4. Target 3 is absent, so return -1. Values must be distinct; an unrotated array or a single element is also valid.
Linear scan: video explanation
nums = [4, 5, 6, 7, 0, 1, 2], target = 0 → 4
Prefer reading? Follow the steps below.
- Visit indices 0 through n - 1. At each index, compare nums[i] with target.
- When they match, return i immediately. For target 0 in [4,5,6,7,0,1,2], the first match is at index 4.
- Return -1 only after the entire loop finishes without a match. Putting this return inside the loop would stop after just one failed comparison.
Time complexity · O(n)
Worst-case time complexity is O(n): a missing target or a match at the last index requires n comparisons.
Space complexity · O(1)
Only the loop index is stored. No copied array is needed: O(1) extra space.
Binary search: video explanation
nums = [4, 5, 6, 7, 0, 1, 2], target = 0 → 4
Prefer reading? Follow the steps below.
- Set left = 0 and right = len(nums) - 1. While left <= right, calculate mid. If nums[mid] equals target, return mid immediately.
- If nums[left] <= nums[mid], the left half is sorted. Keep it only when nums[left] <= target < nums[mid]: set right = mid - 1. Otherwise set left = mid + 1.
- Otherwise the right half is sorted. If nums[mid] < target <= nums[right], set left = mid + 1; otherwise set right = mid - 1. The checked middle can be excluded.
- If left passes right, the target is absent: return -1. For target 0 in [4,5,6,7,0,1,2], mid visits indices 3, 5, and 4, where the match is found.
Unlike a linear scan, binary search discards a whole half at once. Distinct values guarantee that the sorted half can be identified. Do not sort the input: that would change the original indices.
Time complexity · O(log n)
Each unsuccessful iteration roughly halves the search range: O(log n) time.
Space complexity · O(1)
Only left, right, and mid are stored. No sorting, recursion, or copied array is needed: O(1) extra space.