Intermittent search processes switch between local Brownian search events and ballistic relocation phases. We demonstrate analytically and numerically in one dimension that when relocation times are Lévy distributed, resulting in a Lévy walk dynamics, the search process significantly outperforms the previously investigated case of exponentially distributed relocation times: The resulting Lévy walks reduce oversampling and thus further optimize the intermittent search strategy in the critical situation of rare targets. We also show that a searching agent that uses the Lévy strategy is much less sensitive to the target density, which would require considerably less adaptation by the searcher.