Search in Rotated Sorted Array

Medium

Binary Search

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 (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

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 in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1

Input: nums = [4,5,6,7,0,1,2], target = 0

Output: 4

Explanation: 0 is found at index 4.

Example 2

Input: nums = [4,5,6,7,0,1,2], target = 3

Output: -1

Explanation: 3 is not in the array.

Example 3

Input: nums = [1], target = 0

Output: -1

Explanation: 0 is not in the array.

Constraints

•1 <= nums.length <= 5000
•-10^4 <= nums[i] <= 10^4
•All values of nums are unique.
•nums is an ascending array that is possibly rotated.
•-10^4 <= target <= 10^4

Show Hints (3)

Hint 1: In a rotated sorted array, at least one half is always sorted. Identify which half is sorted.

Hint 2: If nums[left] <= nums[mid], the left half is sorted. Otherwise, the right half is sorted.

Hint 3: Check if the target lies within the sorted half. If so, search there; otherwise, search the other half.

Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor

Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?