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.
