I promise I'm not starting another religious battle, I'm just curious, what would you do instead? How would you have the search work? I'm assuming it would have to be an always-present software button. Or perhaps sliding to the left or right. Or maybe a gesture?

It may take up physical space, but the dedicated search button on my phone helps here, and I use it for this exact thing almost daily, so I'm glad it's there.

I think Apple has done nearly all they can here. They've carried through on their UI where you slide all the way and you get search (like on the home screens).