テーブルからの検索一番近いインデックスを取得

質問

こんにちは。
floatのテーブルからどこに一番近いかを知りたいのですがどのようにしたらよろしいのでしようか。
単純に二分探索でやってみましたが検索順序の関係で必ずしも近いところになりません。

------------------------------------------------------------------
int binSearch( float fKey, const float* tblfData, int nNumData )
{
int nFirst = 0 ;
int nLast = nNumData - 1 ;
int nComp ;
float nComped ;

// 探索範囲がなくなったら終了
while( nLast - nFirst > 0 )
{
nComp = ( nFirst + nLast ) / 2 ;
nComped = tblfData[ nComp ] - fKey ;

if(fabsf( nComped ) <= FLT_EPSILON )
{
return nComp ;
}

if(nComped <= 0 )
{
nFirst = nComp + 1 ;
}
else
{
nLast = nComp - 1 ;
}
}

if(nLast - nFirst < 0 )
{
return nLast ;
}

return nFirst ;
}

int _tmain(int argc, _TCHAR* argv[])
{
float tblsData[ 10 ] ;

tblsData[ 0 ] = 0.000f ;
tblsData[ 1 ] = 0.025f ;
tblsData[ 2 ] = 0.050f ;
tblsData[ 3 ] = 0.075f ;
tblsData[ 4 ] = 0.100f ;
tblsData[ 5 ] = 0.125f ;
tblsData[ 6 ] = 0.150f ;
tblsData[ 7 ] = 0.175f ;
tblsData[ 8 ] = 0.200f ;
tblsData[ 9 ] = 0.225f ;

int i ;
float fKey = -0.01f ;
int nRet ;

for( i=0; i<40; i++ )
{
nRet = binSearch( fKey, tblsData, 10 ) ;
if( nRet >= 0 )
{
printf( "%.3f : %d : %.3f\n", fKey, nRet, tblsData[ nRet ] ) ;
}
else
{
printf( "%.3f :error\n", fKey ) ;
}

fKey += 0.01f ;
}

return 0 ;
}
------------------------------------------------------------------
上記のソースで0.060のとき0.050に近いのでbinSearchの戻り値は2を期待したいのですが、
3が返ってきてしまいます。

二分探索しか知りませんでしたので試してみましたが他の方法でもっと適切なのがありましたら
教えていただけないでしょうか。

回答No.1

noname#212058

以下の2か所を直せば良いかと。

・1か所目：binSearch メソッドの while の条件
　while( nLast - nFirst > 1 )
　⇒ 探索するのは「値と一致するデータ」ではなく「値が存在する区分(範囲)」
　　 なので、条件はゼロではなく 1 になります。

・2か所目：binSearch メソッドの最後の値を返すところの条件
　if ( fabsf( tblfData[nLast] - fKey ) <= fabsf( tblfData[nFirst] - fKey ) )
　{
　　return nLast ;
　}
　return nFirst ;
　⇒ nLast と nFirst でより探索値に近いほうを選ばなくてはなりません。

お礼

早々の返答をありがとうございます。
定時して頂いた方法でうまくいきました。
考察が足りませんでした。
助かりました。