Question: Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M >> N and N large enough to span multiple disks. Algorithm to beat O(log n) bonus points for constant time algorithm

Solution: This problem can be solved using bitmaps.bitmap will be an array (say b_array) where we have one bit per M possible number. If we use a character array to store bitmaps, b_array size will be M/8, since 1 char can store 8 bits. Bitmap array will be initialized to zero first. Now for each of the N numbers its corresponding bit should be turned on(1). Corresponding bit for 'n' can be found as follows:
base = n/8; (base is the char whose certain bit needs to be set)

offset = 1 << (n mod 8); (offset is the bit to be set)

b_array[base] |= offset; (I set the particular bit)

Once this is done of all N numbers, given a number m,
we can first find corresponding bit offset and check whether it is one.

base = m/8; (base is the char whose certain bit needs to be set)

offset = 1 << (m mod 8); (offset is the bit to be set)

if (b_array[base] & offset)
// found the number
else
//number could not be found