[algogeeks] Re: Infinite Array
We can use the following stategy: We consider range = 1 and search for given X among those 1 nos, if not found i.e. if X>a[range-1] , we increase range = range*2. If such right end is found , where a[range-1] > X, then we are sure that X is somewhere b/w index [0, range-1] . And now do simple binary search. So, complexity = finding the apt. right end. + finding X = log n + log n = log n Shruti On Sep 30, 10:52 pm, Adi Srikanth wrote: > if its an array, you can get the size of an array from sizeof(array) divided > by size of element typethen we can perform binary search > > Regards, > Adi Srikanth. > Personal Pages: adisrikanth.co.nr > > > > > > > > On Fri, Sep 30, 2011 at 8:47 PM, Don wrote: > > @Ashima: It is a hypothetical question assuming an infinite array, > > which of course requires infinite memory. So don't worry about the > > compiler and other practical considerations. In real life the mass of > > the memory would cause it to collapse into a singularity long before > > the compiler would become an issue. Because we know that the array is > > sorted, we'll need a binary search at some point. But at first we > > don't know the bounds of the search. We must first find an index in > > the array which contains a value greater than or equal to the value > > we're searching for. Then we can do a binary search. To find that > > index, you could start at i=1 and double i until A[i] >= the value you > > are searching for. My method uses something like Newton's Method which > > will converge more quickly in some cases. It assumes that the slope is > > fairly consistent, which may or may not be a good assumption. > > > Don > > > On Sep 30, 10:00 am, "Ashima ." wrote: > > > isnt this quest a lil wrong. coz suppose if i dnt know the length of an > > > array,then how will i access the last element of the array.in such a > > > case,i will almost traverse the whole memory and still not stop. coz > > > compiler does not give array out of bound exception. > > > Ashima > > > M.Sc.(Tech)Information Systems > > > 4th year > > > BITS Pilani > > > Rajasthan > > > > On Fri, Sep 30, 2011 at 6:06 PM, pssaravanan > > > wrote: > > > > > If the length of the array s not known,v could not apply the binary > > > > search to search for an element. i think following code will produce > > > > better solution. > > > > > i = 0; > > > > for(i = 0;A[i] < p&& A[i] !=NULL;i = (i+1)^2); > > > > j = i; > > > > i = sqrt(i)-1; > > > > applybinarysearch(i,j); > > > > > -- > > > > 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. -- 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.
Re: [algogeeks] Re: Infinite Array
if its an array, you can get the size of an array from sizeof(array) divided by size of element typethen we can perform binary search Regards, Adi Srikanth. Personal Pages: adisrikanth.co.nr On Fri, Sep 30, 2011 at 8:47 PM, Don wrote: > @Ashima: It is a hypothetical question assuming an infinite array, > which of course requires infinite memory. So don't worry about the > compiler and other practical considerations. In real life the mass of > the memory would cause it to collapse into a singularity long before > the compiler would become an issue. Because we know that the array is > sorted, we'll need a binary search at some point. But at first we > don't know the bounds of the search. We must first find an index in > the array which contains a value greater than or equal to the value > we're searching for. Then we can do a binary search. To find that > index, you could start at i=1 and double i until A[i] >= the value you > are searching for. My method uses something like Newton's Method which > will converge more quickly in some cases. It assumes that the slope is > fairly consistent, which may or may not be a good assumption. > > Don > > On Sep 30, 10:00 am, "Ashima ." wrote: > > isnt this quest a lil wrong. coz suppose if i dnt know the length of an > > array,then how will i access the last element of the array.in such a > > case,i will almost traverse the whole memory and still not stop. coz > > compiler does not give array out of bound exception. > > Ashima > > M.Sc.(Tech)Information Systems > > 4th year > > BITS Pilani > > Rajasthan > > > > On Fri, Sep 30, 2011 at 6:06 PM, pssaravanan > > wrote: > > > > > If the length of the array s not known,v could not apply the binary > > > search to search for an element. i think following code will produce > > > better solution. > > > > > i = 0; > > > for(i = 0;A[i] < p&& A[i] !=NULL;i = (i+1)^2); > > > j = i; > > > i = sqrt(i)-1; > > > applybinarysearch(i,j); > > > > > -- > > > 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. > > -- 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.
[algogeeks] Re: Infinite Array
@Ashima: It is a hypothetical question assuming an infinite array, which of course requires infinite memory. So don't worry about the compiler and other practical considerations. In real life the mass of the memory would cause it to collapse into a singularity long before the compiler would become an issue. Because we know that the array is sorted, we'll need a binary search at some point. But at first we don't know the bounds of the search. We must first find an index in the array which contains a value greater than or equal to the value we're searching for. Then we can do a binary search. To find that index, you could start at i=1 and double i until A[i] >= the value you are searching for. My method uses something like Newton's Method which will converge more quickly in some cases. It assumes that the slope is fairly consistent, which may or may not be a good assumption. Don On Sep 30, 10:00 am, "Ashima ." wrote: > isnt this quest a lil wrong. coz suppose if i dnt know the length of an > array,then how will i access the last element of the array.in such a > case,i will almost traverse the whole memory and still not stop. coz > compiler does not give array out of bound exception. > Ashima > M.Sc.(Tech)Information Systems > 4th year > BITS Pilani > Rajasthan > > On Fri, Sep 30, 2011 at 6:06 PM, pssaravanan > wrote: > > > If the length of the array s not known,v could not apply the binary > > search to search for an element. i think following code will produce > > better solution. > > > i = 0; > > for(i = 0;A[i] < p&& A[i] !=NULL;i = (i+1)^2); > > j = i; > > i = sqrt(i)-1; > > applybinarysearch(i,j); > > > -- > > 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.
Re: [algogeeks] Re: Infinite Array
isnt this quest a lil wrong. coz suppose if i dnt know the length of an array,then how will i access the last element of the array.in such a case,i will almost traverse the whole memory and still not stop. coz compiler does not give array out of bound exception. Ashima M.Sc.(Tech)Information Systems 4th year BITS Pilani Rajasthan On Fri, Sep 30, 2011 at 6:06 PM, pssaravanan wrote: > If the length of the array s not known,v could not apply the binary > search to search for an element. i think following code will produce > better solution. > > i = 0; > for(i = 0;A[i] < p&& A[i] !=NULL;i = (i+1)^2); > j = i; > i = sqrt(i)-1; > applybinarysearch(i,j); > > -- > 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.
[algogeeks] Re: Infinite Array
If the length of the array s not known,v could not apply the binary search to search for an element. i think following code will produce better solution. i = 0; for(i = 0;A[i] < p&& A[i] !=NULL;i = (i+1)^2); j = i; i = sqrt(i)-1; applybinarysearch(i,j); -- 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.
Re: [algogeeks] Re: Infinite Array
as the array is sorted binary search is the best option... -- 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.
Re: [algogeeks] Re: Infinite Array
@don we dnt hve ny info about arrangement... -- 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.
[algogeeks] Re: Infinite Array
@Don ... optimal one ... +1 On Sep 29, 7:32 pm, Don wrote: > To search for element T in array A[], start at a point p > 0. > If A[p] > T, do a binary search on range 0..p. > Otherwise set p = 1 + p * (T - A[0]) / (A[p] - A[0]). > Repeat until A[p] >= T. Then the current and previous values of p are > an interval containing T (if T is in A). > Do a binary search on that interval. > Don > > On Sep 29, 6:59 am, pooja wrote: > > > Given a sorted Array of infinite length.. what is the most optimum way > > to search for an element. We hane no idea about its length.. > > -- 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.
[algogeeks] Re: Infinite Array
To search for element T in array A[], start at a point p > 0. If A[p] > T, do a binary search on range 0..p. Otherwise set p = 1 + p * (T - A[0]) / (A[p] - A[0]). Repeat until A[p] >= T. Then the current and previous values of p are an interval containing T (if T is in A). Do a binary search on that interval. Don On Sep 29, 6:59 am, pooja wrote: > Given a sorted Array of infinite length.. what is the most optimum way > to search for an element. We hane no idea about its length.. -- 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.
