El Comercio on Sunday has lots of accommodation ads. You have to be quick off the mark - I notice there aren't many ads for Barranco. Call the ones you are interested in first thing in the morning and visit as soon as possible afterwards if you decide you want to see the place.
Make sure you have a small sum of money (maybe $50-100) so that if you like the apartment you can offer the owner a "separacion" on the spot. This is a deposit of interest which demonstrates your seriousness.
Another idea is to walk around all the streets that you like and ask all the guachimen (security men) about rentals in the area as they usually know just about everything going on in a neighbourhood. If you don't speak Spanish take a friend along who does!