478. Search in Rotated Sorted Array (With Duplicates)

Given an array that was sorted in ascending order and then rotated at an unknown pivot, and which may contain duplicates, determine whether a target value exists in the array. Return true if present, otherwise false. Input: '[arr], target'.

Input: '[arr], target'.

Output: Boolean — true or false.

Examples

Input: [2,5,6,0,0,1,2], 0
Output: true
Explanation: 0 is present.

Input: [2,5,6,0,0,1,2], 3
Output: false
Explanation: 3 is absent.

Input: [1], 1
Output: true
Explanation: Single element matches.

Constraints

• 1<=n<=5000
• -10^4<=value,target<=10^4
• array rotated, may contain duplicates

Asked by