Point location in a grid.

Hello everyone,
I am tying to see if the following can be done in a faster fashion using
some kind of randomized algorithm perhaps: I have a square grid composed of
hyper cubes, in d dimensions. I would like to find to which particular
hypercube does a general point belong to.
I can use hierarchical data structure like quad tree and that would give me
the answer in (l*2^d) time: where l is the resolution (depth) at which I am
looking at, and d is the dimension of the space.

But I am wondering if there is a faster way: something that gives quick
answer most of the time, or gives correct answer quickly most of the time..

Thanks,
Amit.

.