PARALLEL MULTIPLE SEARCH

Two sequences of items sorted in increasing order are given: a sequence A of size n and a sequence B of size m. It is required to determine, for every item of A, the smallest item of B (if one exists) that is larger than it. In this paper, we present two algorithms for the problem. The first algorithm requires O(log M+ log n) time using n processors in an EREW PRAM. On an EREW PRAM with p (p less-than-or-equal-to min {m, n}) processors, the second algorithm runs in O(log n + n / p) time when m less-than-or-equal-to n, or in O(log m + (n /p)log(2m / n) time when m > n. The second algorithm is optimal.