dsa · medium

Search in Rotated Sorted Array II

nums began as a non-decreasing sequence and was then rotated at an unknown pivot (the pivot may be 0, i.e. no rotation). Duplicates are allowed. Return whether target appears at least once.

Arguments

• nums — non-decreasing sequence after an unknown rotation; duplicates allowed
• target — value to look for

Example

[1,1,2,2,3] is a rotation of 0. target = 2 is present → true.

[2,5,6,0,0,1,2] is [0,0,1,2,2,5,6] rotated so 2 is first. target = 0 sits in the lower run → true. target = 3 is absent → false.

Constraints

1 <= nums.length <= 5000 -10^4 <= nums[i], target <= 10^4 nums is a non-decreasing sequence rotated at an unknown pivot; duplicates allowed Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.

Examples

Example 1

Input:
[1,1,2,2,3]
2

Expected:
true

Example 2

Input:
[2,5,6,0,0,1,2]
0

Expected:
true

Example 3

Input:
[2,5,6,0,0,1,2]
3

Expected:
false

Open in the Dojo editor