The GNOME team has removed type-ahead search (the ability to search files and folders in the currently displayed folder by typing parts of the file/folder name in the window) in Nautilus version 3.6 in 2012.
Canonical (the company behind Ubuntu) had retained the type-ahead search functionality in their separate fork, but as of 2017., they had removed it.
This caused a number of tickets from dissatisfied users of Ubuntu, however this was not met with acceptance by Canonical, and so far they have not included the removed functionality in Ubuntu. The GNOME team's position too remains unchanged, with them creating additional tickets to try improve the performance, but those efforts have remained futile for 9 years as of today.
However, a developer (Ľubomír Brindza) has created a patch and also maintains a PPA with the patched nautilus package.
This is a simple tutorial that shows you how to install the patches nautilus package into GNOME with type-ahead search functionality added back.
Add the PPA
sudo add-apt-repository ppa:lubomir-brindza/nautilus-typeahead sudo apt update
Install an update to nautilus
sudo apt install nautilus sudo apt autoremove
Compatibility
This patched nautilus works on Ubuntu 17.10, and onwards, and I have tested it latest on 21.04. It also works on derivatives such as Pop!_OS and Linux Mint. It will probably work also on Debian.
Needless to say, it required that you run the GNOME desktop environment.