Problem Statement: Given a rotated sorted array that may contain duplicate elements, the task is to find the pivot index. The pivot is defined as the index where the sorted array was rotated, and it is the smallest element in the array.
Input : [2,5,6,0,0,1,2]
Output : 3
Input : [2,1]
Output : 1
Input : [2,2,2,3,2,2,2]
Output : 4
Input : [1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1]
Output : 14
I'm facing challenge: In a rotated sorted array with unique elements, identifying the pivot index is straightforward using binary search in O(log n) time. However, when the array contains duplicates, this approach becomes less effective due to the inability to determine which half is sorted. Any insights would be greatly appreciated.
Seems impossible in less than O(n). Consider an array with one 1 and n-1 2s. Indeed, it's impossible to figure out where the 1 is without checking every element.
Oh, I see the intuition now, why it's impossible in less than O(n). Thanks!
Use the same method, but instead of returning when it's >, just decrease. And only return when l == r. It's O(n) worst case, but dont try to do better than what you can't do.