I think in order to in O(logn) we need to find the end point of the sorted sequence. Unless we know more about the unsorted part (ex can unsorted contain small sorted sequences) I do not think we can do it in O(logn). What if I have sequence like.. [1,2,3,4,5,6,0,8,9,10,.......] here n = 6 (but not known the user) m = INF
_dufus On Aug 31, 9:18 pm, "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)?? --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
