We adopt a global optimization method to predict two-dimensional (2D) nanostructures through the particle-swarm optimization (PSO) algorithm. By performing PSO simulations, we predict new stable structures of 2D boron-carbon (B-C) compounds for a wide range of boron concentrations. Our calculations show that: (1) All 2D B-C compounds are metallic except for BC(3) which is a magic case where the isolation of carbon six-membered ring by boron atoms results in a semi-conducting behavior. (2) For C-rich B-C compounds, the most stable 2D structures can be viewed as boron doped graphene structures, where boron atoms typically form 1D zigzag chains except for BC(3) in which boron atoms are uniformly distributed. (3) The most stable 2D structure of BC has alternative carbon and boron ribbons with strong in-between B-C bonds, which possesses a high thermal stability above 2000 K. (4) For B-rich 2D B-C compounds, there is a novel planar-tetracoordinate carbon motif with an approximate C(2v) symmetry.