You may not have downloaded any search engine, but you might have downloaded and installed a small software, like Typing Master or some such, and the search engine got installed through that. Many of these setups of small softwares are bundled with such stuff. I think these unwanted programs are called PUPs (Potentially Unwanted Programs). I have a licensed version of Windows and Kaspersky, and one day I found myself infected with one of these. It would keep showing me ads for online shopping. I think it had got installed with some mobile backup software I had installed recently. I tried ADWcleaner, and Malwarebytes Free; they found the infection but couldn't remove it. Kaspersky all this time just sat silently as if nothing was wrong. From what I know, antivirus companies allow some of these PUPs because of legal reasons.
I refreshed Firefox, uninstalled and reinstalled it, but nothing worked. Finally I had to do a format reinstall. As bssunilreddy said, you'll probably have to format and reinstall Windows. You should of course try ADWcleaner and Malwarebytes first; maybe they'll clean the infection on your PC.
If your computer came with backup CDs, or you yourself took a system backup in the beginning, you could use that to reinstall the backup image. If not, you'll have to download a Windows ISO and all the drivers for your computer, and then do the format reinstall.
