@Sanjay yeah its the very basic idea that comes in mind but is your index searching log n ? i think no !! if yes then tell me how?
On Fri, Aug 19, 2011 at 11:24 PM, Sanjay Rajpal <srn...@gmail.com> wrote: > 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 <srn...@gmail.com> 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 <sagarpar...@gmail.com>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 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?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 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?hl=en. > -- **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 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?hl=en.
