Вы можете сделать что-то вроде этого:
def search_contact():
list_contacts()
search = input("please enter first_name : ")
mycursor = mydb.cursor()
mycursor.execute("select * from contacts where first_name LIKE %s", ('%' + search + '%',))
if mycursor.fetchone():
print("yes record found ")
else :
print("no record found ")
Приведенный выше код проверяет, получил ли курсор хотя бы одну запись. Есть более эффективные способы сделать это в SQL (например, используя EXISTS), но это должно работать. Ключевым моментом является то, что вам нужно выяснить, запросил ли запрос какую-либо строку из базы данных.