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 less than or equal to m. We cons ider the problem of determining, for each element A(j), j = 1, 2, ..., n, the unique element B(i), 0 less than or equal to i less than or eq ual to m, such that B(i) less than or equal to A(j) < B(i + 1) (with B (0) = -infinity and B(m + 1) = +infinity). We present an efficient par allel algorithm for solving this problem in O(log m) time using O(n lo g(m/n)/log m) EREW PRAM processors. Our algorithm improves the previou sly known results on either the time or processor complexity, and enab les us to solve several other problems optimally on the EREW PRAM.