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 $a$1≤a2≤...≤an to locate a specified value t.

Structure:

FUNCTION subprograms
User Entry Names: LOCATI, LOCATF

Usage:

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

has the INTEGER value according to the description below.

IA,A
( INTEGER,REAL) One-dimensional array. The numbers IA(j) or A(j) must form a non-decreasing sequence for $j=1,2,...,N$ .
N
( INTEGER) Number n of elements in array IA or A.
IT,T
( INTEGER,REAL) Search value t.
Depending on four possible outcomes of the search, each subprogram returns the following value L $\left(a =IA$ or A, $t =IT$ or T):
 $a$j= t for some $j$ with $1 \le j \le N$ $L=j$ $t < a$1 $L = 0$ $a$k< t < ak+1 for some $k$ with $1 \le k \le N-1$ $L=-k$ $a$n< 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.

Method:

Repeated bisection of the subscript range.

Notes:

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