@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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.