I forgot to mention one thing, at each comparison, store the index at which we searched previously.
Sanju :) On Fri, Aug 19, 2011 at 10:53 AM, Sanjay Rajpal <[email protected]> wrote: > You can do it very easily. > > I assume array is sorted and contains integers. > > Say start at position 1, if value at that index is equal to the value to be > found, return index. > else if value at that index is greater than the value to be found, we got > an interval to search in. > else(value at that index is smaller than the value to be found) > search at location 10,then 100, then 1000 till you find an interval. > > Once you find an interval, perform Binary Search on this and get element in > O(log n). > > Got it ? > > Sanju > :) > > > > On Fri, Aug 19, 2011 at 10:48 AM, sagar pareek <[email protected]>wrote: > >> HI, >> >> I have encountered a problem :- >> >> You have an array of *UNKNOWN *length . And you have to find an element >> in O(log(n)) time without using any extra space. >> >> -- >> **Regards >> SAGAR PAREEK >> COMPUTER SCIENCE AND ENGINEERING >> NIT ALLAHABAD >> >> -- >> 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. >> > > -- 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.
