Android идет со способом сделать Полнотекстовый поиск?
Я знаю, это даже не возможный искать контакты полем примечаний, будучи Google поисковая компания, но я был бы разочарован, если нет никакого API для этого.
Самый простой способ обеспечить полнотекстовый поиск - использовать FTS3 в SQLite