Search in a rotated sorted array
Problem
A sorted array of distinct values was rotated at some unknown pivot (for example [0,1,2,4,5,6,7] became [4,5,6,7,0,1,2]). Return the index of target, or −1 if it is absent, in O(log n) time.
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
Test cases
Case 1
Input: [4,5,6,7,0,1,2], 0 Expected: 4
Case 2
Input: [4,5,6,7,0,1,2], 3 Expected: -1
Case 3
Input: [1], 0 Expected: -1
Case 4
Input: [3,1], 1 Expected: 1
View solutionHide solution1 approach
1. Modified binary search
Time O(log n)Space O(1)
One half [lo..mid] or [mid..hi] is always sorted. Check whether target lies in the sorted half and recurse there.
function search(nums, target) { let lo = 0, hi = nums.length - 1; while (lo <= hi) { const mid = (lo + hi) >> 1; if (nums[mid] === target) return mid; if (nums[lo] <= nums[mid]) { // left half sorted if (nums[lo] <= target && target < nums[mid]) hi = mid - 1; else lo = mid + 1; } else { // right half sorted if (nums[mid] < target && target <= nums[hi]) lo = mid + 1; else hi = mid - 1; } } return -1;}