Migration of immune cells within the human body allows them to fulfill their main function of detecting pathogens. Adopting an optimal navigation and search strategy by these cells is of crucial importance to achieve an efficient immune response. Analyzing the dynamics of dendritic cells in our in vitro experiments reveals that the directional persistence of these cells is highly correlated with their migration speed, and that the persistence-speed coupling enables the migrating cells to reduce their search time. We introduce theoretically a new class of random search optimization problems by minimizing the mean first-passage time (MFPT) with respect to the strength of the coupling between influential parameters such as speed and persistence length. We derive an analytical expression for the MFPT in a confined geometry and verify that the correlated motion improves the search efficiency if the mean persistence length is sufficiently shorter than the confinement size. In contrast, a positive persistence-speed correlation even increases the MFPT at long persistence length regime, thus, such a strategy is disadvantageous for highly persistent active agents.