According to recent studies (Amin et al 2008 Phys. Rev. Lett. 100 060503), the effect of a thermal bath may improve the performance of a quantum adiabatic search algorithm. In this paper, we compare the effects of such a thermal environment on the algorithm performance with those of a structured environment similar to the one encountered in systems coupled to an electromagnetic field that exists within a photonic crystal. Whereas for all the parameter regimes explored here, the algorithm performance is worsened by contact with a thermal environment, the picture appears to be different when one considers a structured environment. In this case we show that by tuning the environment parameters to certain regimes, the algorithm performance can actually be improved with respect to the closed system case. Additionally, the relevance of considering the dissipation rates as complex quantities is discussed in both cases. More specifically, we find that the imaginary part of the rates cannot be neglected with the usual argument that it simply amounts to an energy shift and in fact influences crucially the system dynamics.