Search in Rotated Sorted Array Hard 0 attempts
LeetCode ↗

Search in Rotated Sorted Array

Hard Sorting&Searching LeetCode

An array that was originally sorted in ascending order with all-distinct values has been rotated at some unknown pivot. Given this rotated array nums and a value target, find the index of target in the array, or return -1 if it isn't present.

Input Format
Implement search(nums, target). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

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
Constraints
  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i] <= 10^4
  • All values are unique
Test Cases (2)
Case 1
Args: [[4,5,6,7,0,1,2],0] Expected: 4
Case 2
Args: [[4,5,6,7,0,1,2],3] Expected: -1
Topics
Sorting&Searching

Modified Binary Search

javascript
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]) {
      if (target >= nums[lo] && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      if (target > nums[mid] && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

Time: O(log n) | Space: O(1)

Saved in this browser only. Private to you.

JavaScript