The group structure of the 2-dimensional sidelobe-invariant transformations for binary arrays is characterized. The design of an efficient exhaustive backtracking search algorithm, which exploits such group structure to reduce the search space and, in the meantime, applies the partially determined autocorrelation values as backtracking conditions, is presented. As a consequence of applying the algorithm, all optimal binary arrays with minimum peak sidelobe levels consisting of up to 49 elements are obtained and tabulated.