Given a sorted rotated array, the rotation factor is unknown to you, write a program to find an element in such array in O(log(N)) time and without using any auxiliary space.
Input : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};
key = 3 //The element to be searched.
Output : 8 //index of 3
PLEASE DON’T SUGGEST ANY APPROACH WITH THE TIME COMPLEXITY HIGHER THAN MENTIONED ABOVE
Which part of article is troubling you dear?
What they essentially did, is searching for the ‘pivot’ element, or in other words the maximum valued element. Lets say our initial array was-
{1,2,3,4,5,6,7,8,9,10}
After rotation suppose it is-
{4,5,6,7,8,9,10,1,2,3}
Now we can observe that we cannot directly apply binary search on this array as its unsorted. But the key observation which they used was that, look at maximum element/pivot element. Look at the 2 subarrays from {4…10} and{1…3}.
Essentially these 2 subarrays are sorted. We can use binary search in them. Now all we need to decide is in which sub-array the element is lying. That we can decide easily by-
if(k>=arr[0] &&k<=arr[pivot])//pivot stores index of pivot element
Here we simply checked if value of a is in range of [arr[0],arr[pivot]], if yes, then you have to search that array (adjust high accordingly) else we have to look at the other subarray (adjust low accordingly). This can be accomplished with a simple binary search.
In case of any doubt, do contact me 
Just google it.
What do you mean by rotation factor? Is it number of times the array is rotated?
if array is [1,2,3] and rotation factor is 1 then resulting array becomes[3,1,2]. We are given rotated array and rotation factor is not known.
clear??
It’s simple ;
Just follow the steps and understand that first
First set two variable i.e “start” and “end” and then put them at the first index of the array and at the last index of the array respectively.
perform a while untill “start” remains less than equals to “end” i.e while(start<=end)
inside the loop find the middle element of the array i.e mid = (start+end)/2;
if the target element is equals to the middle element then return the mid.
Till now we did the basic binary search algorithm. Now we need to modify the binary search
If the middle element is not the key then we will check the left side if sorted or not i.e (start<mid).
if the left part is sorted then we will check does the element lies in the left part or not i.e (key >= start && key < mid). if yes then bring the “end” to the mid-1 position else bring the “start” to the mid+1 position if it is not. i.e end = mid-1; or start = mid+1;
if the left part is not sorted then it’s absolute sure that the right part is sorted and we need to check if the element lies in the right part or not i.e (key>mid && key<=end). if yes then bring the start to the mid+1 position else bring the end to the mid-1 position if it is not.
return -1 if the element is not found.
You can understand better after viewing the image
Still if any doubts comes then contact me here 
myLInkedin_ID
