PARALLEL BINARY SEARCH WITH DELAYED READ CONFLICTS
Henk Meijer, Selim G. Akl · International Journal of High Speed Computing · 1990
Given two sorted arrays, A (of size n) and B (of size m) where n≤m, it is required to determine for every element of A its position within B. A parallel algorithm is presented to solve this problem on the exclusive-read exclusive-write parallel random access machine (EREW PRAM). The algorithm uses p processors and runs in time. When and n≤mα, with 0<α<1, the cost of the algorithm, i.e. its running time multiplied by the number of processors it uses, matches the running time of the fastest known sequential algorithm for this problem.