Searching the contact record

I'd really like to be able to search for EITHER first or last name or both of a contact, without having to show the Full Name field in the contact record.

Currently the search is not intuitive enough IMHO.