Given a circular right shifted sorted array with n elements. (Assume the number of shifts to be 'k', k is unknown here). It has been asked to search for a key in the array in log n time.
Example.
Given Circular Right Shifted Sorted Array : 8 9 10 1 2 3 4 5 6 7
Search key 5.
Please note that the time complexity should be log n for the algorithm.
My Approach : Using binary search would give log n time complexity, however, we need a sorted array for that. But a shifted array loses its sorted order after the shift and sorting it again in log n time complexity is the part which I am not getting. Please note that 'k' is unknown here.
Can we even solve this in log n time complexity?
Thanking you in anticipation.
