The Dividing Rectangles (DIRECT) algorithm is a deterministic optimization method to explore optimal solutions by repeatedly dividing a given hyperrectangle search space into subhyperrectangles. Herein, we propose a structure search method for atomic clusters based on the DIRECT algorithm in combination with a gradient-based local optimizer to enable an efficient structure search in high-dimensional search spaces. We use the Z-matrix representation for defining the hyperrectangle search space, in which the bond lengths, bond angles, and dihedral angles specify a cluster structure. To evaluate its performance, we applied the proposed method to the Lennard-Jones clusters and two kinds of real atomic clusters with many metastable structures, i.e., phosphorus and sulfur clusters, and compared the results with those of conventional methods. The proposed method exhibits a higher efficiency than random search and a comparable efficiency to basin hopping.