+1 Gene With regards,
Praveen Raj DCE-IT 3rd yr 9999735993 [email protected] On Wed, Sep 28, 2011 at 1:36 AM, Gene <[email protected]> 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 <[email protected]> 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 [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.
