Find in a Shifted Sorted Array

Medium

There was an array of distinct integers sorted in increasing order. It may have been shifted cyclically: some tail was moved to the front. For example, [1, 4, 6, 8, 9] could have become [8, 9, 1, 4, 6]. The result is the array values. Return the index of value in values, or -1 if it is not there. Your solution must run in O(log n).

Example 1

values=[15, 18, 22, 3, 7, 11], value=7 → 4

The sorted list [3, 7, 11, 15, 18, 22] was shifted to start at 15. The 7 is at index 4.

Example 2

values=[15, 18, 22, 3, 7, 11], value=16 → -1

There is no 16, so the answer is -1.

Example 3

values=[2, 9], value=2 → 0

Constraints

1 ≤ len(values) ≤ 5000
-10⁴ ≤ values[i], value ≤ 10⁴
All numbers in values are distinct
values is an increasing array, possibly shifted cyclically

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search

Similar problems

First and Last Copy Medium Find in a Row-Chained Grid Medium Find in a Shifted Array With Repeats Medium Minimum of a Shifted List Medium The Lone Summit Medium

Input

values=[15, 18, 22, 3, 7, 11], value=7

Expected

Run checks the first 3 tests in your browser. Submit checks all 125 tests on the server, hidden ones included.