Heh, I do the same thing with songs on my iPod for running. I try to have a cadence of about 170-180 bpm, so I look for songs either at 170-180 bpm or 85-90 bpm. The only difference is when you hit the beat when you step. So, for example, the song “Cherub Rock” is about 85 bpm. So I time my steps to each eight note. With something like “I’m a Believer” by the Monkees (about 180 bpm), I time my steps to each quarter note.
Similarly “Ain’t No Sunshine,” when I looked at the lead sheets, is typically noted as 80 bpm (and that is exactly how I would notate it myself). But you can step to it (or write it out) as 160 bpm, if you’d like.