You should use the same connection encoding as your database before executing queries.
If you're using PDO, just set the connection encoding as:
$encoding = "utf8"; //replace this value with the character encoding you're using
$pdo = new PDO("mysql:host=host;dbname=my_db;charset=$encoding", $user, $pass);
If you're using MYSQLI, use mysqli_set_charset
:
$encoding = "utf8"; //Use your encode here
$con = mysqli_connect("host",$user,$pass,"my_db");
mysqli_set_charset($con, $encoding);
Edit~
You may need also to use Accent insensitive collation (UTF8_GENERAL_CI) in your database.
I believe your problem is already solved in the post MySQL charsets and collations: accent insensitive doesn't work