This is generally called a command-not-found handler and are a feature of all the major shells (though the exact details differ, the general idea is to define a function with a specific reserved name), and most majors distros have ones that can be installed, even if they aren't by default.

I wrote my own (much faster) such handler for Arch Linux. I even wrote a blog post about the design: https://vorpal.se/posts/2025/mar/25/filkoll-the-fastest-comm...