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 nondecreasing integer or real numbers $a$_{1}≤a_{2}≤...≤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.
$a$_{j}= t for some $j$ with $1\; \le j\; \le N$  $L=j$

$t\; <\; a$_{1}  $L\; =\; 0$

$a$_{k}< t < a_{k+1} for some $k$ with $1\; \le k\; \le N1$  $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.
$\u2022$