[pfdietz]

The van Emde Boas data structure lets you do searches in sets of integers in O(loglogn) time, if the integers have O(log n) bits.