Ho una serie di float, ordinati dal più piccolo al più grande, e devo essere in grado di scegliere il float più vicino maggiore o minore di un valore di input passato. Questo valore di input non è necessariamente presente come valore nella matrice.
Un approccio ingenuo sarebbe fare una semplice ricerca lineare attraverso l'array. Potrebbe apparire come questo:
void FindClosestFloatsInArray( float input, std::vector<float> array,
float *min_out, float *max_out )
{
assert( input >= array[0] && input < array[ array.size()-1 ] );
for( int i = 1; i < array.size(); i++ )
{
if ( array[i] >= input )
{
*min = array[i-1];
*max = array[i];
}
}
}
Ma ovviamente quando l'array diventa più grande, questo diventerà più lento e lento.
Qualcuno ha un'idea di un algoritmo che mi permetterebbe di trovare questi dati in modo più ottimale? Sono già passato a una ricerca binaria, che ha migliorato un po 'le cose, ma è comunque molto più lenta di quanto mi piacerebbe, e dal momento che non sto cercando un valore specifico che esiste nell'array, non può mai terminare presto.
Ulteriori informazioni: i valori in virgola mobile nell'array non sono necessariamente distribuiti in modo uniforme (ovvero, la matrice potrebbe essere costituita dai valori "1.f, 2.f, 3.f, 4.f, 100.f, 1200.f, 1203.f, 1400.f ".
Sto facendo questa operazione centinaia di migliaia di volte, ma posso fare qualsiasi quantità di pre-elaborazione sulla matrice di float, se migliorerà il tempo di ricerca. Posso assolutamente cambiare usare qualcosa di diverso da un vettore per archiviarli, se ciò sarà di aiuto.