$ apt-get search foo E: Invalid operation search

It's apt-cache search, and it searches full descriptions, not just package names.