Sometimes the fresh water wont bother them enough to run them out.
The best method is Like Bobby said.Use a flash light with a red lense or a red bulb.Find out EXACTLY which rock he's in.
Then take that rock and put it in a bucket of salt water mixed to a S.G. of 1.030 to 1.040.The higher salinity tends to make them try to escape.
Good luck on your hunt and post some pics when you get the little guy.
As a side note.
A lot of LFS will give you a pretty good store credit for a good colorful mantis,and since you say yours is black,It would probably be worth the trouble to catch him alive.