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.
