I have a problem I'd like to code. I have a process which generates numbers 0 through n-1 and I want to stop it when it generates the first repeated element.* I'm looking for a data structure that makes this fast. In particular, adding a new element and testing if an element is in the structure need to be fast. The expected number of insertions is around $\sqrt n$ or actually a bit worse (say $\sqrt{2n}$) because the process slightly favors unique values.
Some kind of self-balancing binary tree seems like the right approach, but maybe there's a better way? For small $n$ I think a bit array would be superior but I'm looking at $n\approx10^9$ which is too large for that to be practical I think.
* Actually, it doesn't need to stop right away -- if it's more efficient you can generate elements in blocks and check every now and then.
This is a CS question but too basic for cstheory.stackexchange and probably insufficiently applied for stackoverflow.