# Search an element in array in Asymptote

In asymptote, I have two arrays

``````int[ ] a = {1, 2, 3, 4 };
int[] b = {2, 3 };
``````

I would like to get the intersection of these two arrays i.e `1, 4`. I can write a function to do this, but is there a builtin alternative. Also `search` and `find` function seem to have non-standard type signature/behavior.

``````int find(bool[], int n=1)
``````

returns the index of the nth true value or -1 if not found. If n is negative, search backwards from the end of the array for the -nth

I don't know how to use it. Ideally i would like to pass the key to find and return true if it is found in array, else false.

``````value; int search(T[] a, T key)
``````

For built-in ordered types T, searches a sorted array a of n elements for k, returning the index i if a[i] <= key < a[i+1], -1 if key is less than all elements of a, or n-1 if key is greater than or equal to the last element of a.

This return n-1 for a key "which is greater than or equal to" the key which is really odd.

• `find(a == 3)` returns 2, the index of the first occurrence of `3` in `a`. `find(a == 3) > 0` returns `true` iff `a` contains `3`. – Charles Staats Mar 18 '16 at 17:24
• I didn't know that one can use numpy like a == 3 . I'll try and let you know. – Dilawar Mar 19 '16 at 6:22
• @Charles: I just found your comment while trying to figure out how to find if an integer existed in an array of integers. Your code is very simple and useful and, as far as I can tell, not in the documentation. One correction though, is that one should use `find(a == 3) > -1`, because `0` is a valid index of the array. – James Jul 1 '16 at 16:02
• @James: You're correct -- I probably meant `find(a == 3) >= 0`. Technically the functionality is documented, but not in a particularly user-friendly way. (Search that page for the word 'vectorized'.) – Charles Staats Jul 1 '16 at 16:31

TL;DR The expression `find(a == 3) >= 0` will be `true` iff the array `a` contains `3`.

If `a` is sorted, you can do the same thing in two lines using the `search` function; theoretically this is faster (`O(log n)` versus `O(n)`, where `n` is the length of `a`):

``````int ii = search(a, 3);
bool a_contains_3 = (ii >= 0 && a[ii] == 3);
``````

You can use the `find` function here with one additional piece of information from the documentation:

Asymptote includes a full set of vectorized array instructions for arithmetic (including self) and logical operations. These element-by-element instructions are implemented in C++ code for speed. Given

``````real[] a={1,2};
real[] b={3,2};
``````

then `a == b` and `a >= 2` both evaluate to the vector `{false, true}`. To test whether all components of `a` and `b` agree, use the boolean function `all(a == b)`. One can also use conditionals like `(a >= 2) ? a : b`, which returns the array `{3,2}`, or `(a >= 2) ? a : null`, which returns the array {2}.

In particular, `a == 3` will be broadcast, returning an array of booleans whose index `i` entry tells you whether `a[i] == 3`. Then, following the behavior quoted in the question, `find(a==3)` will return the index of the first entry of `a` equal to `3`, or `-1` if there is no such entry. So `find(a == 3) >= 0` returns `true` iff the array `a` contains the element `2`.

Using this, you can create the following intersect function that probably works (although I haven't actually tested to make sure it compiles or runs correctly):

``````int[] intersect(int[] a, int[] b) {
int[] intersection;
for (var w : a)
if (find(b == w) >= 0) intersection.push(w);
return intersection;
}
``````

Here's an alternate approach that is faster in terms of big-O notation, but probably slower for many practical examples. (Again, I haven't tested to make sure it compiles, much less works correctly.)

``````int[] intersect(int[] a, int[] b) {
int sorted[], unsorted[], intersection[];
// Sort the shorter array:
if (a.length < b.length) {
sorted = sort(a);  // Does not alter the original array.
unsorted = b;
} else {
sorted = sort(b);  // Does not alter the original array.
unsorted = a;
}
// Iterate through the longer array and save the elements that are also
// in the shorter array.
for (var w : unsorted) {
int ii = search(sorted, w);
if (ii >= 0 && sorted[ii] == w) intersection.push(w);
}
return intersection;
}
``````