Search in Rotated Sorted Array Hard 0 attempts
LeetCode ↗

Search in Rotated Sorted Array

Hard Sorting&Searching LeetCode

Search for target in a rotated sorted array. Return its index, or -1.

Example: nums = [4,5,6,7,0,1,2], target = 0 → Output: 4

Sample Input
—
Sample Output
—
Constraints
  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i] <= 10^4
  • All values are unique
Test Cases
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

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