topic Re: search an ordered table in Intel® Fortran Compiler

search an ordered table

Mike896 — Sat, 04 Oct 2008 04:14:10 GMT

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

Re: search an ordered table

TimP — Sat, 04 Oct 2008 14:03:47 GMT

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

Re: search an ordered table

edr — Sat, 04 Oct 2008 22:02:09 GMT

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.

Re: search an ordered table

DavidWhite — Mon, 06 Oct 2008 01:07:13 GMT

You can locate the position in the array using something like

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

Re: search an ordered table

Mike896 — Mon, 06 Oct 2008 02:02:13 GMT

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

Re: search an ordered table

Jugoslav_Dujic — Mon, 06 Oct 2008 06:50:44 GMT

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.

Re: search an ordered table

g_f_thomas — Tue, 07 Oct 2008 00:24:29 GMT

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

Re: search an ordered table

ArturGuzik — Tue, 07 Oct 2008 01:29:38 GMT

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.

Re: search an ordered table

Mike896 — Tue, 07 Oct 2008 02:00:01 GMT

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

Re: search an ordered table

ArturGuzik — Tue, 07 Oct 2008 03:46:32 GMT

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.

Re: search an ordered table

Mike896 — Tue, 07 Oct 2008 05:51:29 GMT

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

Thank you for your reply.

Mike

Re: search an ordered table

ArturGuzik — Tue, 07 Oct 2008 08:10:31 GMT

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.

Re: search an ordered table

Mike896 — Wed, 08 Oct 2008 00:27:38 GMT

Thank you for your information.

I've found it and it works.

Mike