Since, I don't have strong algorithmic background my question may sound a litlle odd. Please correct me, if so.
I have quite a large bitmap (~100 Million bits) (e.g.
100100101001010001001...010010). The bitmap is just an example, it doesn't have to start with
1 or end with
Now, I need to choose randomly any
0-bit from the bitmap and retrieve it's position. Memory is not an issue in my case, I can maintain a few copies of the bitmap, if necessary. But the acceptable complexity of the algorithm would be linear or
O(n lnn) in the worst case. Couldn't you advice a direction to move to? I'll appreciate any advices or refernces to some related resources.