こんな感じで不定間隔で昇順の配列があります
int[] a = {1,3,7,10,12,20,24,33};
このとき指定した値に一番近い要素の番号を得たいと思ってます
たとえば、3なら1、6なら2、16なら4(中間値なら小さい方)、という具合です

今は配列を走査し
・一致した要素があればその番号
・要素間の範囲に入ってた場合は大きい値と小さい値の差分を計算して差分の小さい方の要素番号
としてるのですが、配列aの要素数が多く(実際には2000くらい)、指定される値も10万個ほどあるので
処理にかなり時間がかかってしまいます

指定される値をソートしてブロック単位で…等とも考えたのてすが、データの仕様上、無理なようです

効率のよいアルゴリズムとかAPI、ありますか?