Search in a rotated sorted array

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}