Mam tablicę liczb zmiennoprzecinkowych, posortowanych od najmniejszej do największej, i muszę być w stanie wybrać najbliższy zmiennoprzecinkowy większy lub mniejszy od przekazanej wartości wejściowej. Ta wartość wejściowa niekoniecznie występuje jako wartość w tablicy.
Naiwnym podejściem byłoby proste przeszukiwanie liniowe tablicy. Może to wyglądać tak:
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];
}
}
}Ale oczywiście w miarę powiększania się tablicy, będzie to coraz wolniejsze.
Czy ktoś ma pomysł na algorytm, który pozwoliłby mi znaleźć te dane bardziej optymalnie? Już przeszedłem na wyszukiwanie binarne, które nieco poprawiło sytuację, ale wciąż jest o wiele wolniejsze niż bym chciał, a ponieważ tak naprawdę nie szukam konkretnej wartości, która istnieje w tablicy, nigdy nie może się zakończyć wcześnie.
Więcej informacji: Wartości zmiennoprzecinkowe w tablicy niekoniecznie są rozmieszczone równomiernie (tzn. Tablica może składać się z wartości „1.f, 2.f, 3.f, 4.f, 100.f, 1200.f , 1203.f, 1400.f ”.
Robię tę operację setki tysięcy razy, ale mogę wykonać dowolne przetwarzanie wstępne na tablicy pływaków, jeśli poprawi to czas wyszukiwania. Absolutnie mogę zmienić, aby użyć czegoś innego niż wektor do ich przechowywania, jeśli to pomoże.