Re: Search Algorithm
--- Bojan Baros <bojan@blis.dyndns.org> wrote:
> Sergio Basurto Juarez said:
> > First of all, I want to leave clear that I know
> that
> > the question that I am asking for, does not have
> to do
> > with this list, but I dare to ask this question
> here
> > because I am sure that here are a lot of good
> > programming and scientisitics guys and may be one
> of
> > you can help me.
> >
> > I am programming a function to search in an array,
> I
> > know there is the binarysearch algorithm, an other
> > good methods to search, but I want something that
> does
> > not take to long.
> >
> > my array is in the form like:
> >
> > myarray[1002] = 7507003101473;
> > myarray[1003] = 7507003101473;
> > myarray[1004] = 7507003101473;
> > myarray[1005] = 7507003101473;
> > myarray[1006] = 7507003101473;
> > myarray[1007] = 7507003101473;
> > myarray[1008] = 7507003101473;
> > myarray[1015] = 7507003101473;
> > myarray[1016] = 7507003101473;
> > myarray[1019] = 7507003101473;
> > .
> > .
> > .
> > myarray[8240] = 7507003182403;
> >
> > The array is formed dinamically from a file.
> >
> > I am wondering if there is some way to find a
> specific
> > value with a derivative method or something like
> that
> > . I found at www.nist.gov/dads/HTML and algorithm
> that
> > implements
> > the Newton Raphson method the formula is:
> > x0 = 0, x1= n-1, i = 1 and v is the array
> >
> > xi+1 = xi - (v[xi]-k) * (xi - xi-1)/(v[xi] -
> > v[xi-1]).
> >
> > but since the formula uses the values of the array
> > and the values that my array have are too big the
> > xi+1(the next indes) goes out of range.
> >
> > I will appreciate any help or point to a source of
> > information.
> >
> Newton Raphson is used to find an x-axis intercept
> (or a specific target
> value) of a function. I don't think it is quite
> suitable for your
> problem.
>
> What I would do is create a hash table that will
> produce a near-unique ID
> for every element of the array. You can than use
> this key to find the
> exact element (or a small set of elements) in only
> few steps.
>
> Bojan
>
Ok I just wondering if there are some mathematics that
can get me the result without use of a Hash Table.
I was trying the Newton Raphson method because I found
this:
"Definition: Search a sorted array by estimating the
next position to check based on the values at the two
previous positions checked.
See also binary search, interpolation search.
Note: It is called "secant search" because it uses the
secant of the function at two successive points to
approximate the derivative in the Newton-Raphson
formula.
To find a key k in an array v with indexes from 0 to
n-1, begin with x0 = 0, x1 = n-1, and i = 1. Compute
the next position with
xi+1 = xi - (v[xi]-k) * (xi - xi-1)/(v[xi] - v[xi-1]).
If this lies outside the range, a different method
(e.g., midpoint of the range) must be used to get the
next position.
Although the theoretical execution time is better than
interpolation search or binary search, coding is
tricky, and the gains from faster convergence are
offset by higher costs per iteration.
Richard Harter <cri@tiac.net> January 2001.
Author: PEB"
at: http://www.nist.gov/dads/HTML/secantSearch.html
Thank you.
=====
--
Sergio Basurto J.
If I have seen further it is by standing on the
shoulders of giants. (Isaac Newton)
--
__________________________________
Do you Yahoo!?
Check out the new Yahoo! Front Page.
www.yahoo.com
Reply to: