Yeah, that's the most efficient way.
You should get a Master ball before anything else though.
Or like what Napoleon suggested.
What you do is:
1) Fly to Slateport City
2) Walk up to the biking area, there's a small patch of grass there
3) Use a Repel, and walk around. If nothing, go in the biking area and come back
(By the way, you should get the [Aero?] bike, the one that jumps to make things easier.