Sublogarithmic searching without multiplications

We show that a unit-cost RAM with word length w can maintain an ordered set of w-bit integers (or binary strings) under the operations search, insert, delete, nearest neighbour in O(/spl radic/(logn)) worst-case time and range queries in O(/spl radic/(logn)+size of output) worst-case time. The operations rely on AC/sup 0/ instructions only, thereby solving an open problem posed by Fredman and Willard. The data structure is simple. We also present a static data structure that can process a set of /spl Theta/O(logn) searches in O(lognloglogn) time.