I was thinking pretty much along the same lines. The OP, however, seems to want it both compact and fast. Binary search will likely not satisfy the latter requirement. Couple links I googled up that might be of interest here:

• cache-oblivious-algorithms
• what-prevents-van-emde-boas-trees...