how to find a device that was turned off

You cannot.

phone stolen or lost

Please  look at this Apple article and my additional advice below it:

 If your iPhone, iPad or iPod touch is lost or stolen – Apple Support

Tracking lost or stolen phones

The 'Find My' tracking is to help you discover if you left your phone in the office or the restaurant. Lost or Stolen phones are rarely ever seen again.

Risk mitigation

Get your provider to 

Cancel your SIM.

Send you a replacement SIM on same number.

You can then put the SIM in another iPhone to get the codes you will need.

Phishing warning

Its possible for a thief to obtain your phone number particularly if you did not have a PIN set on the SIM.  So do not respond to texts to sign into your account! They are NOT from Apple!

 Recognize and avoid phishing messages, phony support calls, and other scams - Apple Support

Resign to the fact that if you had a passcode set and you do not provide your Apple ID via phishing texts then your data is safe but you will never see the phone again.

 Find My

Learn more about how use the Find My app.