how can there be multiple spikes and valleys?? say 1 2 3 4 5 6 7 if you rotate it once with rotation index 3 4 5 6 7 1 2 3 then again with index 2 6 7 1 2 3 4 5 So the multiple times rotation just means that the index of rotation is more then 1.
On Fri, Apr 6, 2012 at 7:02 AM, Ashish Goel <[email protected]> wrote: > code needed… > > not ble to visualize what to do if there are too many spikes and valleys > in the multiple times rotated array, is that possible?? > > On Sep 28, 2011, at 1:36 AM, Gene 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. > > -- 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.
