search an ordered table

[Mike896]

Hi

Does anybody know if there is a function in IMSL that is able to search an ordered table.

I've found SRCH which can search a sorted vector for a given scalar and return its index.

However, I'd like to have a return of an index J such that given a value x is between arrayxx(J) and xx(J+1).

Thank you very much.

Mike

[TimP]

Why not look at 1 or 2 browser search hits? e.g. http://www.pdas.com/binsrch.htm

[edr]

Just write a quick binary search routine....since it is an ordered table that will probably be quicker (to execute) than most other methods.

Ed.R.

[DavidWhite · Accepted solution]

You can locate the position in the array using something like

J = MAXLOC(XX,MASK=XX.LT.X)

[Mike896]

Quoting - David White

You can locate the position in the array using something like

J = MAXLOC(XX,MASK=XX.LT.X)

This is a very interesting method. Simple and work.

Thank you and all.

Mike

[Jugoslav_Dujic]

Quoting - Mike896

This is a very interesting method. Simple and work.

But not very efficient. Since your vector is already sorted, binary search would work much faster. For small datasets, however, simplicity is a virtue.

[g_f_thomas]

FWIT, a sorted list of N can be optimally searched in N^1/2 steps via Grover's algorithm. However, the computer to do it has yet to be built.

Gerry

[ArturGuzik]

Mike,

from Numerical Recipes: "In most cases, when all is said and done, it is hard to do better than bisection,
which will find the right place in the table in about log_2(n) tries."

Take a look at routine "locate.f90". It does exactly what you're looking for. See Chapter 3, Interpolation and Extrapolation, specifically 3.4 "How to Search an Ordered Table" . Description and source code is on page 111 (of Fortran 77 edition), or 1045 (as function) in Fotran 90 Edition.

A.

[Mike896]

Yes, I have seen it. In fact, I used to use locate.f (mine is f77 version.But recently as I build the Numerical-Recipe library with IVF, there are lot of problems related to functions as an actual argument. Until now, I don't know how to solve this problem.

Therefore, I go to seek IMSL, but thereare no similar functions/subroutines.

thank you and all of you.

Mike

[ArturGuzik]

Mike,

I'm using this particular routine in several applications and it works perfectly. The F90 version is a function (unlike subroutine from F77). Do you have it? I saw that there is a newer NR (C++ edition only) available.

I have had a not-so-great experience with IMSL a few years back, so usually go the other way, trying to replace their "stuff" with something else.

A.

[Mike896]

Mine is f77 version. I don't have f90 version and C++ version.

Thank you for your reply.

Mike

[ArturGuzik]

Mike,

I'm not sure you need/want this but link to pdf (book and source code) is here so you can take a look. Section B3.

A.

[Mike896]

Thank you for your information.

I've found it and it works.

Mike