Tengo una matriz que indica si una tarjeta está en uso:

int used[52];

Esta es una manera terrible de elegir una tarjeta al azar si tengo muchas tarjetas usadas:

do {
  card = rand() % 52;
} while (used[card]);

ya que si solo tengo 3-4 tarjetas sin usar, me llevará una eternidad encontrarlas.

Se me ocurrió esto:

 int card;
 int k = 0;
 int numUsed = 0;
 for (k=0; k < 52; ++k) {
   if (used[k]) numUsed += 1;
 }
 if (numUsed == 52) return -1;
 card = rand() % (52 - numUsed);

 for (k=0; k < 52; ++k) {
   if (used[k]) continue;
   if (card == 0) return k;
   card -= 1;
 }

que creo que funciona mejor si la cubierta está llena, pero funciona peor cuando la cubierta está vacía, ya que tengo que pasar por dos bucles.

¿Cuál es la forma más eficiente de hacer esto?