All organisms with sexual reproduction undergo a process of mating. In mate search, both sexes mutually optimize their encounters, raising a new question of the random search problem that has often considered optimization in the context of foraging for food. Here we show that a population with sexually dimorphic movement patterns achieves the highest individual mating success under limited lifetime. Extensive simulations and analytical solutions specified the conditions under which the sexual dimorphism of diffusivity in movements is advantageous. The mutual searchers with limited lifetime need to balance the speed and accuracy of finding their mates, and the dimorphic movements can solve this trade-off. We further demonstrate that the sexual dimorphism can evolve from an initial sexually monomorphic population. Our results can be applied to any systems involving pairwise interactions between agents and emphasize the importance of considering mutual optimization in problems of random search.