searching, global memory access binary searching?

Hi there,
The problem I am facing is:
I have a table like this

11.22 0.73
11.482 0.407
11.749 0.285
12.023 0.22
12.303 0.18

In my kernel, I need to look up ( search ) for some values in this table. For example, I may be given the key value 12.105, need to get the corresponding data value.

I think I should save this table to constant memory, and do binary searching for the the values I needed and do the interpolation. Then the searching time will be log(N),
this means I may need log(N) times global memory access----------think it is going to kill my performance.

It is not a issue in CPU but seems it is a problem for CUDA…

wondering if anybody have good idea about this?