$request = mysql_query($query);
$result = mysql_num_rows($request);
if($result) {
while( $result = mysql_fetch_assoc($request) ) {
　foreach($result as $key => $value) {
　　print "{$key} : {$value}";
　}
}
} else {
　print "該当なし";
}

検索結果がない場合を考慮して、
mysql_num_rowsで検索結果数を確認しているのですが、
mysql_fetch_assocも使っていて、
mysql_num_rowsは、非効率な処理をしているのではないかという気になります。

検索結果がない場合の処理として、
もっと最適な方法はありますでしょうか？

スピード重視ですので、PDOなどを利用する予定はありません。