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. The paper presents two parallel algorithms for the problem. The first algorithm requires O(logm+logn) time using n processors on an EREW PRAM. On an EREW PRAM with p (p⩽min{m, n}) processors, the second algorithm runs in O(logn+_p/ⁿ) time when m⩽n, or in O(logm+_p/ⁿ log_n/^2m) time when m>n. The second algorithm is optimal