I don't this would work for all cases. Infact the problem is not with your solution but with question statement. An unsorted sequence might contain small sorted sequence interleaved by unsorted sequences. (Nothing in the problem statement rules out this possibility) So if you have something like
1,2,3,4,5,6,7,0,10,11,13.... Algo would fail. _dufus On Sep 2, 11:16 pm, Ramaswamy R <[email protected]> wrote: > It is possible. > This will be a binary search as well. Only instead of matching the value > with the mid value you'd check the following > > bool c1 = array[left] < array[mid] > bool c2 = array[mid] < array[right] > > if both the conditions are true then, then the entire range is sorted > if c1 is true and c2 is NOT true, then search for it in mid<->right range > else > search for it in left <-> mid > > Just like in binary search we'd reduce the problem space by 2 in every step > resulting in O(log N) complexity. > > On Mon, Aug 31, 2009 at 9:18 AM, shashi @mnnit < > > [email protected]> wrote: > > > there is an array with m elements... > > > it is known that first n elements are sorted... but dont know what is > > 'n'.... n<<m > > > given an element x find whether x is there in sorted elements. > > > Can this be done in O(log n)?? > > -- > Yesterday is History. > Tomorrow is a Mystery. > Today is a Gift! That is why it is called the Present :). > > http://sites.google.com/site/ramaswamyr --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
