You are required to find an integer value target in an array arr of non-distinct integers. Before being passed as input to your search function, arr has been processed as follows:

• It has been sorted in non-descending order.

• It has been rotated around some pivot $k$, such that, after rotation, it looks like this: [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]. For example, [10, 30, 40, 42, 42, 47, 78, 90, 901], rotated around pivot $k=5$ becomes [47, 78, 90, 901, 10, 30, 40, 42, 42].

Return TRUE if t exists in the rotated, sorted array arr, and FALSE otherwise, while minimizing the number of operations in the search.

Note: In this problem, the value of $k$ is not passed to your search function.

Constraints

• $1 \leq$ arr.length $\leq 1000$

• $-10^4 \leq$ arr[i] $\leq 10^4$

• arr is guaranteed to be rotated at some pivot index.

• $-10^4 \leq$ t $\leq 10^4$

The challenge is efficiently searching for a target value within a rotated array. Even when the array is rotated, at least one part will still be sorted. To find the target, the algorithm uses a modified binary search. During the search, the algorithm first identifies which segment of the array (either the left or right half) is sorted. Based on the sorted segment, the algorithm determines if the target value lies within that segment. If it does, the search is narrowed to that half of the array. If not, the search continues in the other half. When the array contains duplicates, it can make it harder to identify the sorted segment. In such cases, the algorithm adjusts the search space by skipping over the duplicates.

The steps of the algorithm are as follows:

1. Initialize two pointers, left at the beginning of the array and right at the end.

2. Calculate the middle index mid.

3. Check if arr[mid] is equal to target. If yes, return TRUE.

4. If arr[left] to arr[mid] is sorted:

   1. Check if the target lies within this range. If so, move the right pointer to mid - 1.

   2. Otherwise, move the left pointer to mid + 1.

5. If arr[mid] to arr[right] is sorted:

   1. Check if target lies within this range. If yes, move the left pointer to mid + 1.

   2. Otherwise, move the right pointer to mid - 1.

6. If the array contains duplicates, the algorithm can’t determine which part is sorted due to the elements at left, mid, and right being equal. Specifically, this happens when arr[left] == arr[mid] && arr[mid] == arr[right]. In such cases, it’s difficult to determine whether the sorted segment is on the left or right side. To overcome this, the algorithm increments the left pointer by one (left += 1) to skip over the duplicate, thereby reducing the search space. This step helps the algorithm progress even when it encounters a block of identical elements that could otherwise prevent it from identifying the sorted segment. Alternatively, the algorithm can handle duplicates by decrementing the right pointer (right -= 1).

7. Repeat steps $2-6$ until left exceeds right.

8. If the loop exits without finding the target, return FALSE.

Let’s look at the following illustration to get a better understanding of the solution: