Check non-existence of number

Devise an algorithm to 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 (You may read one number at a time from the list but it will not be possible to store all of them in the memory).

Solution :

1. The solution is using bitmaps (arrays of bits)
2. Initialization will take O(N) but checking for existence will be done in O(1)
3. Bitmap array will be char[M/8] since a char is 8 bits long

Complexities :

• Time : O(N) in initialization, O(1) in access
• Space : O(M)

Code :
// init() is called once for all numbers in list one by one to initialize the bitmap

void init(int[] bitmap, int M, int num){

int base = num/8;
int offset = 1 << (n%8);
bitmap[base] |= offset;

}

bool exists(int[] bitmap, int M, int num){

int base = num/8;
int offset = 1 << (n%8);
return (bitmap[base] & offset);

}