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 0
.
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.