It is easy.. find the point where it is rotated to get 14<->1 O(log(n)) since 2<14 that means u have to find it in subarray [123].. do a binary search here o(long(n)) final 2*O(log(n))...
On Fri, Jun 8, 2012 at 7:44 PM, Dave <[email protected]> wrote: > @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. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. 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.
