CareerCup

The amount "i" rotated, can be found in o(n) time. After finding "i", standard binary search can be applied with an additional mapping to the index. Index k has to mapped to (k-i+n)%n before indexing the array

Pseodocode:array index starts from 0,1,...
------------------------------------------------------------
p=given number to find
N=size of array
k=index of smallest element //amount of rotation in O(N) time
l=left index=k
r=right index = (k-1+N)%N
l1=transform(l)=(l-k+N)%N
r1=transform(r)=(r-k+N)%N

while(l1<=r1)
{
mid1=(l1+r1)/2
mid=inverseTransform(mid1)=(mid+k)%N
if(p== [mid]) break
//p occurs at index mid. [mid] indicates value at index=mid
if(p> [mid])
{
l1=mid1+1
}
else
{
r1=mid1-1
}
}

//code to check if p doesn't exist in array
-----------------------------------------------------
Note: variables l,r,mid indicates the indices of the given array
and variable l1,r1,mid1 are indices if the array would have not
been rotated,i.e. the lowest index (zero) contains smallest element

Don't u think the runtime will be O(n+logn) if the amount of rotation is unknown?

You should be able to take advantage of the fact that the array is sorted and I think you can use an idea similar to binary search to find rotation i in O(log(n)) time.

Binary search with some extra conditions will be the way to find the element in log n time.

Divide and conquer. Compare first, middle, last to decide which half contains the max. This allows to find the shift i in O(lgN). Then use the shift and do binary search. Also O(lgN). Overall, it is O(lgN).

n= total size
Find(a,low,high,i,val)
{
if a[i]>a[(i+1)%n]
Left Rotation with i=n-i;
else if a[i]<a[i+1]
Right Rotation with i=i;
else if a[i]=a[i+1]
return Find(a,low,high,i-1);
mid= ((low+high)/2 + i)%n;
low = (low+i)%n;
high = (high+i)%n;
if(val < a[mid])
return ((low==(mid-1+n)%n) ? -1: Find(low, (mid-1+n)%n));
else if(val > a[mid])
return (((mid+1)%n==high)?-1:Find((mid+1)%n,high));
else if(val == a[mid])
return mid;
}

Please comment. Didnt tested thorougly