Search

bin, binr

Syntax: x bin y (atomic)
Syntax: x binr y (atomic)

Binary search 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.

It uses 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.

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 is an atomic function of y, i.e. the result has the same shape as y.

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

bin and ? on 3 columns find all equijoins on the first 2 cols and then do bin or ? respectively on the 3rd column. bin assumes the 3rd 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 is not unique 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

distinct

Syntax: distinct x

Returns the distinct (unique) items of x.

q)distinct 2 3 7 3 5 3
2 3 7 5
Returns the distinct rows of a table.
q)distinct flip `a`b`c!(1 2 1;2 3 2;"aba")
a b c
-----
1 2 a
2 3 b
It does not use comparison tolerance:
q)\P 14
q)distinct 2 + 0f,10 xexp -13
2 2.0000000000001
.Q.fu (apply unique)

? (find)

Syntax: x?y

Where:

  • x is a list
  • y is any data object

returns the lowest index for which y matches an item of x – the ‘first occurrence’. If there is no match the result is the count of x. Comparisons are exact, and are not subject to comparison tolerance.

q)w:10 -8 3 5 -1 2 3
q)w?-8
1
q)w[1]
-8
q)w?3 / the first occurrence of 3
2
q)w?17 / not found
7
q)w[7]
0N
q)"abcde"?"d"
3
Find is type-specific relative to x. Where:

  • x is a simple list and y a list whose atoms are all the same type as x, the result corresponds to x item-by-item.

    q)rt:(10 5 -1;-8;3 17)
    q)i:w?rt
    q)i
    (0 3 4;1;2 7)
    q)w[i]
    (10 5 -1;-8;3 0N)
    

  • x is a list of lists and y is a simple list, items of x are matched with the whole of y.

    q)u:("abcde";10 2 -6;(2 3;`ab))
    q)u?10 2 -6
    1
    q)u?"abcde"
    0
    

  • where x is a mixed list then items of x are matched with items of y.

    q)u?(2 3;`ab)
    3 3
    
    In this case find matches items of x with 2 3 and `ab , not (2 3;ab) ``.

Find is rank-sensitive

x?y can’t deal with mixed-rank x. If rank x is n then x?y looks for objects of rank n-1.

2 3?2 3#til 6  / looks for rank 0 objects
(0 1 2;4 5)?2 3#til 6 / looks for rank 1 objects
A solution to find (2 3;`ab) is
q)f:{where x~\:y}
q)f[u;(2 3;`ab)]
,2

Searching tables

Where x is a table then y must be a compatible record (dictionary or list) or table. That is, each column of x, paired with the corresponding item of y, must be valid arguments of find.

q)\l sp.q
q)sp?(`s1;`p4;200)
3
q)sp?`s`p`qty!(`s2;`p5;450)
12

in

Syntax: x in y

Returns a boolean indicating:

  • where the first item of y is an atom, which items of x are also items of y (list, same count as x)
  • otherwise, whether x is an item of y (atom)
q)1 3 7 6 4 in 5 4 1 6        / which of x are in y
10011b
q)1 2 in (9;(1 2;3 4))        / none of x are in y
00b
q)1 2 in (1 2;9)              / 1 2 is an item of y
1b
q)1 2 in ((1 2;3 4);9)        / 1 2 is not an item of y
0b
q)(1 2;3 4) in ((1 2;3 4);9)  / x is an item of y
1b

in is often used with select

q)\l sp.q
q)select from p where city in `paris`rome
p | name  color weight city
--| ------------------------
p2| bolt  green 17     paris
p3| screw blue  17     rome
p5| cam   blue  12     paris

See also: except inter union within

within

Syntax: x within y (uniform)

Where x is an atom or list of sortable type/s and

  • y is an ordered pair (i.e. (</)y is true) of the same type, the result is a boolean for each item of x indicating whether it is within the inclusive bounds given by y.

    q)1 3 10 6 4 within 2 6
    01011b
    q)"acyxmpu" within "br"  / chars are ordered
    0100110b
    q)select sym from ([]sym:`dd`ccc`ccc) where sym within `c`d
    sym
    ---
    ccc
    ccc
    

  • y is a pair of lists of length n, and x a list of length n or an atom, the result is a boolean list of length n.

    q)5 within (1 2 6;3 5 7)
    010b
    q)2 5 6 within (1 2 6;3 5 7)
    111b
    q)(1 3 10 6 4;"acyxmpu") within ((2;"b");(6;"r"))
    01011b
    0100110b
    

See also: except in inter union