Topic · Binary SearchMedium
Search in Rotated Sorted Array
Understand the problem
Given an integer array nums of distinct values, sorted in ascending order and then rotated at an unknown pivot, and an integer target, return the index of target if it is found, otherwise return -1. The solution must run in O(log n).
Example:
ts
nums = [4, 5, 6, 7, 0, 1, 2], target = 0
output = 4 // nums[4] = 0
nums = [4, 5, 6, 7, 0, 1, 2], target = 3
output = -1 // 3 is not in the array
nums = [1], target = 0
output = -1A rotated array means: there exists some k such that nums = [nums[k], ..., nums[n-1], nums[0], ..., nums[k-1]].
Basic approach
O(n) time, O(1) spacets
function search(nums: number[], target: number): number {
return nums.indexOf(target) // O(n) linear scan
}Why this approach is slow:
A linear scan violates the O(log n) requirement.
You need to exploit a property: even after rotation, one half of the array is always still in sorted order.
Unlock the optimal solution, the step-by-step trace and related questions
See the full step-by-step trace, Big-O and edge cases.