It is not currently possible to search only undeleted notes without either emptying the Recently Deleted folder, or without locking all the notes you've deleted.

Recently Deleted folder

Deleted notes are placed in the Recently Deleted folder and, by default they will remain there for 30 days before they are automatically deleted. This applies to both macOS and iOS. So, if you manually delete them from there it will solve the problem, as they don't still exist to be searched.

However, if you don't want empty the Recently Deleted folder, another option is locking your notes.

Locking notes

By locking notes you will prevent them from being searchable. However, while the contents of these notes do not appear in search results, the titles of these notes will.

You can lock any notes so long as they're not already in the Recently Deleted folder. So one option would be to lock your notes prior to deleting them.

To lock notes:

1. Select the individual note you want to lock (you cannot lock more than one at a time)
2. Click on the padlock icon in the toolbar
3. Select the Lock This Note option
4. Enter your password (Note: If you've never used this feature before you will need to create a password. Once this is set, this will be the password you use to lock/unlock all notes in future.)
5. You will now see a padlock icon next to the title of your note. Initially it will be unlocked.
6. You can now lock the selected note by either clicking on the padlock icon in the toolbar or opening the note and clicking on the padlock icon in the notes toolbar.

Once locked, the contents of the note is unsearchable (although the title itself is still searched). This will be the case whether you now delete the note or not.

Below is more general info about searching notes.

Within macOS

In the Notes Help pages there's a page titled Search for notes.

From this page, is the following info:

You can search for specific text in all your notes, notes in a specific account, or in a single note. Your search finds matching text in the body of notes and in the file names of attachments. Your search also finds matching text in text files (such as Pages documents and PDFs) that you’ve attached to your notes. If you’ve locked a note, only the title text appears in the results.

Also included are these tips:

• Search: Enter text in the search field.
• Search in a specific account: Click a folder in the account you want to search, click in the search field, click the magnifying glass , then choose Current Account.
• Search in all accounts: Click in the search field, click the magnifying glass , then choose All Accounts.
• Find text in a note: Click the body of a note to add an insertion point, then choose Edit > Find > Find (or press Command-F). Enter text in the search field that appears.

If you're using macOS Sierra, you can also use Siri to search your notes.

Ask Siri something like: “Show me notes from today”, or “Show me notes about vacation plans”.

Source: Notes > Help > Notes Help and select the Search for notes page.

Within iOS

Assuming you're using iOS 10, its Note app introduced some major enhancements.

From the Use Notes on your iPhone, iPad, and iPod touch page on Apple's website:

Search for a note or attachment

Looking for that note you made last week, last month, or even last year? You can search for a specific note from the top of the Notes list. Scroll to the top of the Notes list to reveal the search field, then enter what you’re looking for. You can also search for attachments. Tap Attachments Browser icon in the lower-left corner to see sketches, photos, links, documents, and other attachments that you’ve added to your notes. To go to the note with the attachment, touch and hold the thumbnail of the attachment, then tap Show in Note.

And of course, you can use Siri (as I mentioned above) to search notes in iOS.