Add a test for empty search

Change-Id: I47e418d6db92fef4afe0d726892d993beccc71e9