When something says to search your deck for cards you should search the deck, make your choice, and shuffle afterward. Once you begin shuffling you may not go back and change your choice unless your opponent allows you to do so.