E106 Binary Search for Element in Ordered Array

Next: E201 Least Squares Up: CERNLIB Previous: E105 Function Interpolation

E106 Binary Search for Element in Ordered Array

Routine ID: E106
Author(s): F. James	Library: KERNLIB
Submitter:	Submitted: 18.10.1974
Language: Fortran	Revised: 27.11.1984

Integer function subprograms LOCATI and LOCATF perform a binary search in an array of non-decreasing integer or real numbers $a$ ₁≤a₂≤...≤a_n 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

(a = IA

or A,

t = IT

or T):

$a$ _j= t for some $j$ with $1 ≤j ≤ N$	$L =j$
$t < a$ ₁	$L = 0$
$a$ _k< t < a_k+1 for some $k$ with $1 ≤k ≤ 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.

$•$

E201

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