Given an integer array arr sorted in non-decreasing order, possibly containing duplicate values, and rotated at an unknown pivot index, determine if a given integer value x exists in arr. Return True if x is present, otherwise return False.
Example 1
Input: arr = [7,8,9,1,2,3,4,5,6], x = 3
Output: True
Explanation: 3 is present in the rotated array.
Example 2
Input: arr = [4,4,5,6,7,0,1,2,4], x = 8
Output: False
Explanation: 8 is not present in the array.
Example 3
Input: arr = [1,1,1,1,1,1,1], x = 1
Output: True
Explanation: 1 is present multiple times.
Example 4
Input: arr = [2,2,2,3,4,2], x = 3
Output: True
Explanation: 3 is present in the rotated array.
Constraints
Case 1
Input: arr = [10,12,15,1,3,5,7,9], x = 5
Expected: True
Case 2
Input: arr = [6,7,8,9,1,2,3,4,5], x = 10
Expected: False
Case 3
Input: arr = [0,0,0,0,0,0,0,0], x = 1
Expected: False
Case 4
Input: arr = [5,6,7,8,9,1,2,3,4], x = 2
Expected: True
Case 5
Input: arr = [3,3,3,3,3,3,3,3], x = 3
Expected: True