--- Bojan Baros <[EMAIL PROTECTED]> 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 <[EMAIL PROTECTED]> 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 -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
