How should I practice Search in a Rotated Sorted Array?

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

Is Search in a Rotated Sorted Array associated with Goldman Sachs?

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

Problem · Array

Search in a Rotated Sorted Array

Learn this problem

● Medium

Goldman SachsFULLTIMEPHONE SCREEN

Problem statement

Given an integer array nums that was sorted in strictly increasing order and then rotated at an unknown pivot, and an integer target, return the index of target.

Return -1 when target does not appear in nums.

All values in nums are distinct. Your solution must run in O(log n) time.

Function

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

Examples

Example 1

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

The target 0 appears at index 4.

Example 2

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

The target 3 is absent, so the result is -1.

Example 3

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

The only array value is 1, so 0 is absent.

Constraints

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums contains distinct values.
nums was sorted in strictly increasing order and rotated at an unknown pivot.
-10^9 <= target <= 10^9