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 <[email protected]>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 <[email protected]> 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 <[email protected]>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 <[email protected]>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 >>>> <[email protected]>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 <[email protected]>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 <[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. >>>>>> >>>>> >>>>> >>>>> >>>>> -- >>>>> **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. >>>> >>> >>> >>> >>> -- >>> **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. >> > > > > -- > **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.
