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 <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.
