Two ways:
brew search forumla

Which is in built however won’t work if you are looking for if it’s not the name of the formula.

This is my script called brew-search

#!/usr/bin/env bash

curl --silent --compressed https://raw.githubusercontent.com/Homebrew/homebrew-command-not-found/master/executables.txt | grep -P "^$1:|[: ]$1( |$)" | grep -Po '^.+(?=:)'

Which can be called by brew-search command

My script works for xxd.

$ brew search xxd
$ brew-search xxd
vim