@Hassan: This is not possible without additional conditions. E.g., you
cannot find the 1 in the array {0,0,0,...,0,1,0,0,...,0} in less than O(n)
time.
But with the condition that the elements of the array are pairwise
distinct, you can use a binary search to find k such that a[k-1] > a[0] and
a[k] < a[0]. Then if x < a[k], do a binary search to find x in {a[k] ...
a[n-1]}; otherwise do a binary search to find x in {a[0] ... a[k]}.
Dave
On Friday, June 8, 2012 8:41:47 AM UTC-5, Hassan Monfared wrote:
> A sorted array of integers is rotated unknown times. find an item in
> O(logn) time and O(1) space complexity.
> for example : 1,2,3,7,10,14 -------rotated 3 times------> 7,10,14,1,2,3
> find 2 in O(logn) time in O(1) space complexity
>
> Regards
> Hassan H. Monfared
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/KD9Hz01ZIJ8J.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
