Hi pharta : " find the point where it is rotated to get 14<->1 O(log(n)) " how can you find rotation point in log(n) ?
On Fri, Jun 8, 2012 at 6:57 PM, partha sarathi Mohanty < [email protected]> wrote: > 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. > -- 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.
