Re: Search Algorithm
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
Reply to: