I don’t know how or where you’re looking, but on the very “Tools and Setup” URL you provided, I can see that all the recommended plugins have direct links to the respective plugins 😀
Are those links not working for you?
–> https://wordpress.org/plugins/log-deprecated-notices/
But note that as this plugin is woefully out of date (tested up to 5.8.10) that’s going to be a really low bar to test against for deprecated functions.
As for the Plugins directory search function, I suspect that the “freshness” of the plugin may be taken into consideration that’s why this old and abandoned plugin doesn’t show up. But it appears when you search with the full name in quotes: “Log Deprecated Notices”

I don’t know how or where you’re looking …
That’s odd, because I explained above in my original message that I was looking for the plugin on the Add Plugins page (as instructed by the official documentation).
… this plugin is woefully out of date …
In that case, perhaps the Theme Handbook shouldn’t recommend installing it. Are the forums not the right place to ask questions about the WP documentation? I looked through the handbook trying to find more explicit instructions about where to post questions/feedback, and didn’t find anything along those lines in the handbook itself, so I fell back on the more generic pointers, which led me here. In my experience, most open-source projects welcome such feedback, but if the WP community doesn’t work that way, I’ll gladly refrain from further engagement. 😅
Try emailing themes@wordpress.org or ask about this in #themes on Slack.
If you want to suggest optimizations to the documentation, I would recommend that you open a ticket here: https://meta.trac.wordpress.org/newticket – in the course of this I would also recommend describing a concrete suggestion for improvement on how it could be done better.
but with the broken search algorithm
The algorithm for searching for plugins uses many different factors to display the best possible results. It is not generally “broken” as you define it, as it is perfectly usable for the vast majority of users. As far as I know, the definition can be found publicly in the repository here: https://github.com/WordPress/wordpress.org/tree/trunk/api.wordpress.org
If you want to suggest optimizations to this, I would recommend that you enter them with concrete ideas as a ticket here: https://meta.trac.wordpress.org/newticket