You shouldn’t use sudo with Homebrew. First run the following to ensure you own everything under /usr/local:
sudo chown -R $(whoami):admin /usr/local
Alternative command for newer macOS version:
sudo chown -R $(whoami) $(brew --prefix)/*
Then reset your Homebrew repo to a clean state:
cd /usr/local && git fetch && git reset --hard origin/master
It should fix your issues.
(replace /usr/local with $(brew --prefix) if you installed Homebrew elsewhere)