:) On Fri, Aug 19, 2011 at 11:43 PM, Sanjay Rajpal <srn...@gmail.com> wrote:
> Thats wat I said, it depends. Searching in the interval will compensate > reaching the index earlier. > So both are almost equivalent. > > Sanju > :) > > > > On Fri, Aug 19, 2011 at 11:12 AM, sagar pareek <sagarpar...@gmail.com>wrote: > >> Well i think it depends... >> because range of x and 10x is more than i and 2i >> no doubt multiple of 10 will give us early index but then to find number >> in b/w indexes is more than of 2^i >> >> >> On Fri, Aug 19, 2011 at 11:38 PM, Sanjay Rajpal <srn...@gmail.com> wrote: >> >>> Multiplication by 10 or 2^i , it depends. >>> >>> Multiplication by 10 will be faster, I think. >>> >>> Sanju >>> :) >>> >>> >>> >>> On Fri, Aug 19, 2011 at 11:05 AM, sagar pareek <sagarpar...@gmail.com>wrote: >>> >>>> hmmm ok >>>> i found a solution in which index searching is done by 2^i >>>> which is more optimal >>>> multiplication by 10 or 2 power i ?? i=0,1,2,3..... >>>> >>>> On Fri, Aug 19, 2011 at 11:30 PM, Sanjay Rajpal <srn...@gmail.com>wrote: >>>> >>>>> See at each step you are multiplying the index to be compared by >>>>> 10(say), this increase is exponential. >>>>> Therefore the search is exponential and complexity is log n. Base >>>>> depends on the factor by which you are multiplying for the next index to >>>>> be >>>>> compared. >>>>> >>>>> Sanju >>>>> :) >>>>> >>>>> >>>>> >>>>> On Fri, Aug 19, 2011 at 10:57 AM, sagar pareek >>>>> <sagarpar...@gmail.com>wrote: >>>>> >>>>>> @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. >>>>>> >>>>> >>>>> -- >>>>> 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. >>>> >>> >>> -- >>> 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. >> > > -- > 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.
