I'm not sure how to get back the search, try what Kev said.
To search, press the Windows (logo) Key, and 'F'. Or, Simply Press F3 when you are on the desktop.
See if the search window opens.
Which virus was it? Maybe we can help in reversing the damage it has caused.
Abhas added 37 Minutes and 44 Seconds later...
Ok, Try this :
Right click on the taskbar. Click on Properties.
In the window that opens, click on the "Start Menu" Tab.
Click on "Customize" Button.
Now Click on the "Advanced" Tab in the window that just opened.
In the List of Start Menu Items, There is an option of "Search" towards the end.
Make sure it is ticked. If it is not, tick it and click Ok on all the screens.
If it is already ticked, Untick it, and click OK on all screens, and then go back and tick it.