HI
THIS WORKED FOR ME - SOLVED THE SEARCH & GROUP ISSUES.
I have the 4S & just installing 9.1. Extremely annoyed at Apple to lost this feature along with all my groups after the installation of this new update. Waited through the 9.0??? etc till 9.1 figuring that they would correct any problems that were created post 8.4.1. Was I wrong. Anyway....................
Tried something to see if it would clear up this problem. It was an intuitive stab in the dark and it worked, Got back the search feature in contacts and also my groups that were deleted after the upgrade to 9.1.
Here is what I did: 1st I signed out of ICloud on my phone but did not delete the files from the phone.Closed any open apps & Reset the phone via holding the locked & home buttons till the Apple logo appeared then release the buttons. Once the phone booted completely I checked to see if the search feature in contact was working. It was & better than before. Next I signed back into ICloud (note ICloud Drive was NOT activated at anytime). After signing back into ICloud I left all the apps off in Icloud, Ie Contacts, Calender etc. except for mail and find my phone. Then I closed any open apps if any were open and once again reset the phone as I did before. Once booted I open Contacts and the search feature was working perfectly. Next I logged in on my computer into ICloud.com to make sure that all the apps were in tacked an they were. Before logging out I went to contacts and created a group called IPhone( name it what you like) and copy some of the contacts to this new group. Closed ICloud.com and went back to the 4S. Next I went back into ICloud and turned on all the apps that were previously off & turned on only the ones that I wanted ICoud to share with all my devices.(This is a personal decision i.e. which ones you want off etc.) Finally I closed all open apps and did a final Reset of my Phone. Once the phone booted completely I open my Contacts and not only was the search feature working great but my groups were back...
Please don't ask me if all the resets were necessary because I can't really say. All I can say is that it worked perfectly for me. Is there a rhyme or reason, um why not ask Apple why this happen in the 1st place.
If this works for you and you want to know how I got on this track please write back & I will be happy to tell you. There was a "method to my madness"LOL Please let me not imply this was my 1st thought........no way went through some hoops for sure! Good Luck
Michael