Animals must move to search for other organisms. One important question is what is the most efficient strategy for searching randomly located or moving objects. Some studies have measured movement patterns of various organisms and have theoretically estimated its searching efficiency. However, as most of the studies on optimal search strategy focused on foraging for food, little is known about efficiency of searching for sexual partners. Here we demonstrate that sexual difference of movement patterns enhances the mating encounter rates. Our simulation by searcher-target model, where we changed the exponent for Lévy walk, demonstrated that the encounter efficiency is maximized when one sex moves more diffusively than the other under some ecologically realistic conditions. We also empirically tracked walking of termite dealates, where males behaved more diffusively than females. These results suggest that moving differently to the other sex can be the mutual optimized strategy for organisms. We will discuss the evolution of sexual dimorphism from the viewpoint of searching efficiency.