Abstract The direct binary search (DBS) algorithm is an efficient method for the generation of binary holograms, but it is also an iterative method involving lengthy computation. Thus, fast non-iterative approaches are more preferred in practice even though they yield poorer results. In this paper, we propose a strategy to drastically reduce the computational time of the DBS algorithm. First, we show that convergence of the conventional DBS algorithm can be significantly improved by optimizing the order in which the pixels are examined. Then, we demonstrate the efficiency of a design based on optimization of multiple small blocks of binary pixels through parallel computation. Since each block can be optimized in parallel utilizing platforms such as those offering cloud computing services, the time to compute the final pattern is determined by the computational time for a single block. The proposed block-partition strategy involves a trade-off between the computation time and the quality of the final hologram. However, it should be noted that simply randomizing the pixel examination order during the DBS procedure reduces the computational time by 67% even without parallel computation. In summary, our proposed method facilitates easier generation of high-quality binary holograms in less time than is required by the conventional DBS.