The new menu Contact Search is located in the Contacts App

When accessing the Contact Search form a new query can be defined by
clicking on the Create button.
To perform a search the search string is required and the Odoo models that
should be searched have to be selected in the dropdown 'Search in model'.

The search results are stored and can be accessed at a later time from the
tree view of 'Contact Search'.