Deleting a contact is supported by 'Swipe to Delete' gesture on a cell, doing that will reveal the 'Delete' action. (also care was taken to be supported during search mode where the results are stripped down based on search)

In general, that is a common now feature on the iOS and by now, users are accustomed on that gesture. Let me know what you think

Thanks!