The spin-wave band structure of a two-dimensional bicomponent magnonic crystal, consisting of Co nanodisks partially embedded in a Permalloy thin film, is experimentally investigated along a high-symmetry direction by Brillouin light scattering. The eigenfrequencies and scattering cross sections are interpreted using plane wave method calculations and micromagnetic simulations. At the boundary of both the first and the second Brillouin zones, we measure a forbidden frequency gap whose width depends on the magnetic contrast between the constituent materials. The modes above and below the gap exhibit resonant spin-precession amplitudes in the complementary regions of periodically varying magnetic parameters. Our findings are key to advance both the physics and the technology of band gap engineering in magnonics.