> My gut was more that it is 2^(number of dimensions) that is important here.

Yes, it's just binary search but applied to every dimension.