Find in a Shifted Array With Repeats

Medium

There was an array of integers sorted in non-decreasing order; numbers may repeat. It was shifted cyclically: some tail (possibly empty) was moved to the front. For example, [0, 2, 2, 5, 7] could have become [5, 7, 0, 2, 2]. The result is the array values. Return True if value appears in values, otherwise False. Use as few steps as you can. Think about how repeats affect the speed compared to the case of distinct numbers.

Example 1

values=[6, 6, 8, 1, 3, 3, 6], value=3 → True

This is [1, 3, 3, 6, 6, 6, 8] shifted to start at a 6. It does contain a 3.

Example 2

values=[6, 6, 8, 1, 3, 3, 6], value=5 → False

There is no 5.

Example 3

values=[4, 4, 4, 0, 4], value=0 → True

Constraints

1 ≤ len(values) ≤ 5000
-10⁴ ≤ values[i], value ≤ 10⁴
values is a non-decreasing array shifted cyclically

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search

Similar problems

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

Input

values=[6, 6, 8, 1, 3, 3, 6], value=3

Expected

True

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