Pattern projection-based 3D measurement systems are widely used for contactless, non-destructive optical 3D shape measurements. In addition, many robot-operated automation tasks require real-time reconstruction of accurate 3D data. In previous works, we have demonstrated 3D scanning based on statistical pattern projection-aided stereo matching between two cameras. One major advantage of this technology is that the actually projected patterns do not have to be known a priori in the reconstruction software. This allows much simpler projector designs and enables high-speed projection. However, to find corresponding pixels between cameras, it is necessary to search the best match amongst all pixels within the geometrically possible image area (that is, within a range on the corresponding epipolar line). The well-established method for this search is to compare each candidate pixel by temporal normalized cross correlation of the brightness value sequences of both pixels. This is computationally expensive and interdicts fast real-time applications on inexpensive computer hardware. We show two variants of our algorithm “Binary Correspondence Search” (BICOS), which solve this task in significantly reduced calculation time. In practice, our algorithm is much faster than traditional, purely cross-correlation-based search while maintaining a similar level of accuracy.