In this paper, a procedure for optimizing two-dimensional (2D) photonic crystals (PhC) is presented. In this procedure, the unit cell of a PhC structure is discretized into small grids and converted into a binary sequence. A direct binary search (DBS) method is then used to search through a terrain of possible solutions in order to find a more optimal one. This process is designed for improving the absolute band gap, opening a new one, for a predefined PBG structure. By applying this procedure on a honeycomb array of dielectric rods in air background, the maximum absolute gap-to-midgap ratio (MAGTMR) is increased to more than twice that of the initial structure. To further prove the validity of this procedure, this procedure is also applied to two best-found hexagonal and square lattice structures. The band gap improvements in these two cases indicate that besides structure type, structure symmetry, fill factor, index contrast, and size, shape and orientation of the constituent objects, there are other unknown factors, which affect the absolute band gap of a photonic crystal as well. The convergence property of this procedure is also discussed in this paper. The idea of this procedure can be applied to find the global optimal solution by using a global optimization algorithm, such as simulated annealing (SA), genetic algorithm (GA).