Nach ca. 7 Arrayzugriffen und ebenso vielen Vergleichen sollte da Ergebnis gefunden sein. Wieso dauert das 250 Takte? Das wären ca. 30 Ticks pro Durchlauf...

http://de.wikipedia.org/wiki/Bin%C3%A4re_Suche

Schneller geht's mit einem inversen Array, das braucht aber dann 1000 Einträge.

Einfach mit dem Suchwert indizieren (nach Test, daß er in den Intervallgrenzen liegt), und du hast den Index 0...90 des nächsten Elements oder das Element selbst, je nach Implementierung.