We present a procedure for optimizing two-dimensional (2D) Photonic Band Gap (PBG) structures. The procedure discretizes the unit cell of a PBG structure into a binary cell and uses Direct Binary Search to search through a terrain of possible solutions in order to find a more optimal one. This process is designed either for improving the absolute band gap or opening a new one, for a predefined PBG structure. By applying the procedure on a honeycomb array of high dielectric objects in an air background, we increased its Maximum Absolute Gap-to-Midgap Ratio (MAGTMR) to more than twice that of the initial structure. To further prove the utility of this procedure, we also present other examples.