Summary: The time complexity of searching a sorted list of n elements in parallel on a coarse grained network of diameter D and consisting of N processors (where n may be much larger than N) is studied. The worst case period and latency of a sequence of pipelined search operations are easily seen to be \(\Omega\) (log n-log N) and \(\Omega (D+\log n-\log N)\), respectively. Since for \(n=N^{1+\Omega (1)}\) the worst-case period is \(\Omega\) (log n) (which can be achieved by a single processor), coarse-grained networks appear to be unsuitable for the search problem. By contrast, it is demonstrated using standard queueing theory techniques that a constant expected period can be achieved provided that \(n=0(N2^ N)\).