Given an integer array arr of length n, which is sorted in non-decreasing order and then rotated at an unknown pivot, and an integer value x, determine if x exists in arr. Return True if x is present, otherwise return False. The array may contain duplicate values.
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,4,4,4,4,4], x = 5
Output: False
Explanation: 5 is not present in the array.
Example 3
Input: arr = [1,2,2,2,3,4,5,0], x = 0
Output: True
Explanation: 0 is present at the last index.
Constraints
Case 1
Input: arr = [10,12,15,1,3,5,7,9], x = 12
Expected: True
Case 2
Input: arr = [2,2,2,3,4,2], x = 3
Expected: True
Case 3
Input: arr = [6,7,8,9,1,2,3,4,5], x = 10
Expected: False
Case 4
Input: arr = [1], x = 1
Expected: True
Case 5
Input: arr = [1], x = 0
Expected: False