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 < shashikantkoshta1...@gmail.com> 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 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 -~----------~----~----~----~------~----~------~--~---
