Thrust vectorized search: Efficiently combine lower_bound and binary_search to find both position and existence

Question

I'm trying to use Thrust to detect if each element of an array can be found in another array and where (both arrays are sorted). I came across the vectorized search routines (lower_bound and binary_search).

lower_bound will return for each value the index where it could be inserted in a list respecting its ordering.

I also need to know if the value is found or not (which can be done with binary_search), not just its position.

Is it possible to achieve both efficiently without making two searches (calling binary_search and then lower_bound)?

I know in the scalar case, lower_bound will return a pointer to end of the array if a value cannot be found, but this does not happens in the vectorized version.

Thanks!

Answer 1

You can check that the element that lower_bound returns is the same as the one you searched for. E.g. given a = {1,3,5} and searching for b = {1,4}, the result will be c = {0,2}. We have a[c[0]] == b[0], so b[0] is in a, but a[c[1]] != b[1] so b[1] is not in a.

(Note that you will need to ensure that you don't make any out-of-bounds memory accesses, since lower_bound can return an index that is beyond the end of the array.)