How should I practice Search in Rotated Sorted Array?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft onsite interview problems in FastPrep.

Is Search in Rotated Sorted Array associated with Microsoft?

FastPrep tags this as a Microsoft onsite interview coding practice problem when the problem catalog has that company and stage context.

Search in Rotated Sorted Array

Microsoft● MediumFULLTIMEONSITE INTERVIEW

Learn

Problem statement

You are given an integer array nums that was originally sorted in strictly increasing order and then possibly rotated at an unknown pivot. All values in nums are distinct.

Given an integer target, return its index in nums. Return -1 when target is absent.

Your algorithm must run in O(log n) time.

Function

search(nums: int[], target: int) → int

Examples

Example 1

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

The value 0 appears at index 4.

Example 2

nums = [4,5,6,7,0,1,2]target = 3return = -1

The value 3 does not appear in the array.

Example 3

nums = [1]target = 0return = -1

The one-element array contains 1, not 0.

Constraints

1 <= nums.length <= 100000
-10^9 <= nums[i], target <= 10^9
All values in nums are distinct.
nums is a rotation of a strictly increasing array.