x bin y,
x binr y,
xis a sorted list
yis a list or atom of the same type
returns the index of the last item in
x which is ≤
y. The result is
y less than the first item of
binr binary search right, introduced in V3.0 2012.07.26, gives the index of the first item in
x which is ≥
They use a binary-search algorithm, which is generally more efficient on large data than the linear-search algorithm used by
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.
r can be interpreted as follows: for an atom
r is an integer atom whose value is either a valid index of
-1. In general:
r[i]=-1 iff y[i]<x r[i]=i iff x[i]<=y[i]<x[i+1]
r[j]=x bin y[j] for all j in index of y
bin gives a half-open interval on the left.
binr are right-atomic: their results have the same count as
? on three columns find all equijoins on the first two cols and then do
? respectively on the third column.
bin assumes the third column is sorted within the equivalence classes of the first two column pairs (but need not be sorted overall).
q)0 2 4 6 8 10 bin 5 2 q)0 2 4 6 8 10 bin -10 0 4 5 6 20 -1 0 2 2 3 5
If the left argument items are not distinct the result is not the same as would be obtained with
q)1 2 3 3 4 bin 2 3 1 3 q)1 2 3 3 4 ? 2 3 1 2
Sorted third column¶
bin detects the special case of three columns with the third column having a sorted attribute. The search is initially constrained by the first column, then by the sorted third column, and then by a linear search through the remaining second column. The performance difference is visible in this example:
q)n:1000000;t:(a:`p#asc n?`2;b:`#asc n?1000;c:asc n?100000) q)\t t bin t 194 q)update`#c from`t; / remove the sort attr from column c q)\t t bin t 3699