DSA problem
Search in Rotated Sorted Array
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 (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], ..., nums[k-1]]. 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. You must write an algorithm with O(log n) runtime complexity.
The crucial observation is that, for any midpoint mid, at least one of the two halves [lo, mid] or [mid, hi] is fully sorted (not crossed by the rotation pivot). Comparing nums[lo] with nums[mid] reveals which: if nums[lo] <= nums[mid], the left half is sorted; otherwise the right half is.
Once you know which half is sorted, you can decide where target could live in O(1): if it is in the sorted half's range, discard the other half; otherwise discard the sorted half. This still halves the window per iteration, preserving O(log n) running time. The whole algorithm is just the classic binary search with an extra branch to handle which side is sorted.
Edge cases worth checking are an unrotated array (k = 0), a fully-rotated-back array, single element inputs, and the target equaling nums[lo] or nums[mid]. Use <= carefully when checking whether a half is sorted; with distinct values nums[lo] <= nums[mid] is the right inequality.
Examples
nums = [4,5,6,7,0,1,2], target = 04nums = [4,5,6,7,0,1,2], target = 3-1nums = [1], target = 0-1Constraints
- 1 <= nums.length <= 5000
- -10^4 <= nums[i] <= 10^4
- All values of nums are unique.
- nums is guaranteed to be rotated at some pivot.
- -10^4 <= target <= 10^4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.