Search in Rotated Sorted Array

MediumBinary Searchrotated-array-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 can assume that all values in the rotated sorted array nums are unique.

The trivial solution runs in O(n) time. Can you write an algorithm that runs in O(log n) time?

Example 1:

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

Example 2:

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

Recommended time and space complexity

The optimal solution has O(log n) time complexity and O(1) space complexity, where n is the size of the input array.


Hint 1

Linear search gives us O(n). To achieve O(log n), think about binary search. How can it be modified to work with a rotated array?


Hint 2

At any point in the array, one half will always be sorted. How can this be used?


Hint 3

By determining which half is sorted, we can check if the target value is within that range. If yes - search there, if no - search the other half.

This problem tests binary search implementation skills and working with sorted arrays. It develops understanding of algorithmic complexity and the ability to find optimal solutions for modified data structures.
solution.js · saved

Input

[3,4,5,6,1,2], 1

Expected Output

4