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 ByteDance phone screen problems in FastPrep.

Is Search in Rotated Sorted Array associated with ByteDance?

FastPrep tags this as a ByteDance phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Search in Rotated Sorted Array

Learn this problem

● Medium

ByteDanceFULLTIMEPHONE SCREEN

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.