next up previous index
Next: E201 Least Squares Up: CERNLIB Previous: E105 Function Interpolation

E106 Binary Search for Element in Ordered Array

Routine ID: E106
Author(s): F. JamesLibrary: KERNLIB
Submitter: Submitted: 18.10.1974
Language: FortranRevised: 27.11.1984

Integer function subprograms LOCATI and LOCATF perform a binary search in an array of non-decreasing integer or real numbers a1≤a2≤...≤an to locate a specified value t.


FUNCTION subprograms
User Entry Names: LOCATI, LOCATF


In any arithmetic expression, LOCATI(IA,N,IT) or LOCATF(A,N,T)

has the INTEGER value according to the description below.

( INTEGER,REAL) One-dimensional array. The numbers IA(j) or A(j) must form a non-decreasing sequence for j=1,2,...,N .
( INTEGER) Number n of elements in array IA or A.
( INTEGER,REAL) Search value t.
Depending on four possible outcomes of the search, each subprogram returns the following value L (a = IA or A, t = IT or T):
aj= t for some j with 1 ≤j ≤N L=j

t < a1 L = 0

ak< t < ak+1 for some k with 1 ≤k ≤N-1 L=-k

an< t L=-N

If the value t occurs more than once in the array a, the result L may correspond to any of the occurrences.


Repeated bisection of the subscript range.


The number of comparisons performed is approximately proportional to lnN . Therefore, for large N the binary search is considerably faster than a sequential search using a DO loop. However, for N less than about 40 a DO loop is faster.


Janne Saarela
Mon Apr 3 15:06:23 METDST 1995