La mejor forma es Match ... against como te explicaron arriba. Primero crea un índice FULLTEXT para los campos NOMBRE Y APELLIDOS de mysql.
Luego ya podrás utilizar match (nombre,apellidos) against ($busqueda).
Buscará la cadena por separado en los dos campos, y pondrá una puntuación en un campo llamado Score, que podrás utilizar para ordenar los resultados por relevancia. Una especie de esto:
Código PHP:
Ver originalSELECT * , MATCH(nombre,apellidos) AGAINST ('{$cadenaBusqueda}') as Score FROM tabla_basededatos WHERE MATCH(nombre,apellidos) AGAINST ('{$cadenaBusqueda}') ORDER BY Score DESC
Suerte!