as in how to find it?
Go to a low level route, use repel, have a level 40 as your lead, then keep running in, going into the grass and moving around of a minute, then running out of the route, then repeat.
As for hunting whether it's shiny, if I'm not mistaken, the PID gets determined the moment you complete the Sapphire fetch quest for Celio at One Island. So before giving the Sapphire to Celio should be your last point.