Busqueda en memoria por mas cercano

[jars]

Hola amigos,
Tengo lo siguiente: Necesito una estructura en la que pueda almacenar los siguientes datos:
TimeOffset :LongWord; (clave)
prevTimeOffset :LongWord; (datos)
PositionOffset :LongWord; (datos)

La clave seria TimeOffset.
El problema se centra en la búsqueda ya que el valor a buscar (x) no es precisamente el almacenado sino uno que sea x > a y x < b.
Ejemplo:

Elemento clave datos
1 2183 0 0E
2 4447 2183 8EBE
3 6720 4447 11DC2
4 8983 6720 1AD26
... ... .... .....

El dato a buscar pej. es 5300, tengo que encontrar la clave 4447, (x > elemento 2 y x < elemento 3) se entiende?
La cantidad de elementos es variable y puede ser bastante grande por eso pensé en alguna tabla hash porque tengo entendido que son las mas rápidas aunque nunca las he usado y no se como hacerlo.

Espero haberme explicado bien y cualquier ayuda será bienvenida.

Gracias
Jorge