I’m doing the dexnav thing and it’s always baltoy or the cactus thing. It’s never gible and I even caught kyogre.
EDIT: Asker is probably referring to Route 111.
Gible is a Hidden Pokemon, which means it's generally going to be harder to find. Cacnea and Baltoy, on the other hand, both have a 20% encounter rate. Finding it the first time is always the hardest, due to having a low Search Level for the Pokemon. You have already defeated Kyogre, so it should show up eventually. You're simply getting bad RNG.