Binary search

x bin  y    bin[x;y]

Where

• x is a sorted list
• y is a list or atom of exactly the same type (no type promotion)

returns the index of the last item in x which is ≤y. The result is -1 for y less than the first item of x. binr binary search right, introduced in V3.0 2012.07.26, gives the index of the first item in x which is ≥y.

They use a binary-search algorithm, which is generally more efficient on large data than the linear-search algorithm used by ? (Find).

The items of x should be sorted ascending although bin does not verify that; if the items are not sorted ascending, the result is undefined. y can be either an atom or a simple list of the same type as the left argument.

The result r can be interpreted as follows: for an atom y, r is an integer atom whose value is either a valid index of x or -1. In general:

r[i]=-1            iff y[i]<x[0]
r[i]=i             iff x[i]<=y[i]<x[i+1]

and

r[j]=x bin y[j]    for all j in index of y

Essentially bin gives a half-open interval on the left.

bin and binr are right-atomic: their results have the same count as y.

bin also operates on tuples and table columns and is the function used in aj and lj.