Implement rotated array binary search with duplicates

Given an integer array nums that is a non-decreasing array rotated an unknown number of times. Duplicates may exist. Implement a function that returns a pair: (rotation_count, leftmost_index_of_target) where rotation_count is the index of the rotation point and leftmost_index_of_target is the smallest index i such that nums[i] == target or -1 if absent. Definitions and constraints:

• Rotation point is the smallest index r such that nums[r] < nums[(r-1+n)%n]. If no such r exists (array already sorted or all equal), rotation_count = 0.
• Time: O(log n) expected; discuss and handle worst-case O(n) when duplicates make direction ambiguous.
• Space: O(1).
• Edge cases: all elements equal; target duplicated across the rotation boundary; n=1; empty array.
• Example: nums = [4,5,5,6,6,1,2,3,3], target=3 → rotation_count=5, leftmost_index_of_target=7.
• Provide: (a) algorithm idea; (b) correctness argument; (c) complexity; (d) thorough unit tests covering edge cases.

Rotated Array: Rotation Count + Leftmost Target Index

Given an integer array nums that is a non-decreasing array rotated an unknown number of times (duplicates may exist), return a pair (rotation_count, leftmost_index_of_target).

• rotation_count is the rotation point: the smallest index r such that nums[r] < nums[(r-1+n)%n]. If no such r exists (the array is already sorted or all elements are equal), rotation_count = 0. This equals the index of the minimum element (the wrap point).
• leftmost_index_of_target is the smallest index i such that nums[i] == target, or -1 if target is absent.

Return the answer as a two-element pair/array [rotation_count, leftmost_index_of_target].

Algorithm idea: The wrap point is the unique 'drop' where a later element is smaller than the element before it; a modified binary search on nums locates it in O(log n) expected time, falling back to a linear scan in the worst case when duplicates make the comparison nums[mid] == nums[hi] ambiguous (you must then shrink the window by one, giving O(n) worst case — e.g. [2,2,2,0,2]). The leftmost occurrence of target can be found with a leftmost-binary-search within the appropriate rotated half, again degrading to O(n) with heavy duplicates.

Example: nums = [4,5,5,6,6,1,2,3,3], target = 3 → rotation_count = 5, leftmost_index_of_target = 7.

Hints

1. The rotation point is the unique index where a value drops below its predecessor (cyclically). It is the index of the minimum element. If there is no drop, the array is sorted and rotation_count = 0.
2. With duplicates, a binary search can hit nums[mid] == nums[hi], making it impossible to tell which half holds the wrap point — shrink the window by one (hi -= 1) and continue. This is what forces O(n) worst case.
3. For the leftmost occurrence of target, do not stop at the first match found by binary search; keep searching to the left (continue toward lower indices) until you find the smallest matching index.