+1 Gene With regards,
Praveen Raj DCE-IT 3rd yr 9999735993 praveen0...@gmail.com On Wed, Sep 28, 2011 at 1:36 AM, Gene <gene.ress...@gmail.com> wrote: > Indeed you must be given that all the array elements are unique or at > least that there are no more than floor(n/2) repeats). Otherwise this > is impossible. The simplest way to think about it is first to search > for i such that a[i] > a[i+1]. At that point you know there are two > sorted ranges a[0]..a[i] and a[i+1] to a[n-1], so you can use regular > binary search on each of these pieces. > > So how to find i? This is itself a binary search. At each stage, > check whether a[0] > a[mid] and a[mid] > a[n-1]. The half that passes > this test contains i. So throw away the other. > > On Sep 27, 10:01 am, Decipher <ankurseth...@gmail.com> wrote: > > A given sorted array is rotated unknown number of times , write a C/C++ > code > > to find an element in the sorted array in O(log n) time . > > > > I know the solution to this problem is through binary search , but don't > > know the exact solution . Please help !! > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > 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. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. 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.
