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.
