On the new iPhone software, you can search for a contact using the first and last name. For instance, if you want to search for Pedro Fernandes, you would write P F (that's P, then a space, then an F). The iPhone will filter out all the contacts with first and last name starting with P and F, and vice-versa. You can further refine the search by typing more letters. This is a great time-saving feature; thanks, Apple!
Bonus hint... on a standard phone (none-Apple) I always stored the names in such a way that you can do this search. So for instance I would have: Pedro Fernandes stored as PFernandes Pedro, Tania Silva stored as TSilva Tania, Daniel Fidalgo stored as DFidalgo Daniel, etc. This enables a quick search through first and last names. So if you are stuck (or by choice) have an old (classic) phone, maybe you find this usefull as well.
Mac OS X Hints
http://hints.macworld.com/article.php?story=20080714142350433