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.
