How should I practice Single-Pass Search in a Rotated Sorted Array?

Start by reading the full statement, solve the visible examples, then compare the pattern against related eBay phone screen problems in FastPrep.

Is Single-Pass Search in a Rotated Sorted Array associated with eBay?

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

Problem · Array

Single-Pass Search in a Rotated Sorted Array

Learn this problem

● Medium

eBayFULLTIMEPHONE SCREEN

Problem statement

An integer array nums was originally sorted in strictly increasing order and then rotated at an unknown pivot. Given nums and an integer target, return the index of target, or -1 if it is absent.

Use one binary-search loop. Do not first locate the pivot and then run a second binary search. Your solution must run in O(log n) time.

Function

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

Examples

Example 1

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

The target 0 is stored at index 4.

Example 2

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

The target does not occur in the array.

Constraints

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