Efficient parallel binary search on sorted arrays, with applications

Let A be a sorted array of n numbers and B a sorted array of m numbers, both in nondecreasing order, with n⩽m. We consider the problem of determining, for each element A(j), j=1, 2, …, n, the unique element B(i), 0⩽i⩽m, such that B(i)⩽A(j)<B(i+1) (with B(0)=-∞ and B(m+1)=+∞). We present an efficient parallel algorithm for solving this problem in O(log m) time using O([nlog (m/n)]/[log m]) EREW PRAM processors. Our algorithm improves the previously known results on either the time or processor complexity, and enables us to solve several other problems optimally on the EREW PRAM