Basic [Search] gives broad results, and is slower due to the process required to accomplish the search.
[Advanced Search] offers several fields that can be used as part of your search:
The greater number of fields used, the finer the search.
A tip: Less is better.
Let me explain:
Fewer fields broadens the search.
If you are getting no results from entering a simple "First Name" and "Last Name", you can broaden the search by trying something like using the first 3 or 4 letters of the name. Sometimes, the lack of results can be attributed to misspellings.
Searching "Notes" - Currently, the best way to perform a "Search" in "Notes" is to run a "Notes" report in CSV format, and perform a "Search" in Excel.