Here is the question I have been struggling to solve lately. Imagine we have two integers $x, y \in \mathbb Z, x \le y$ and $Y = \{ a | a \in \mathbb Z\ and\ x \le a \le y \}$; $X\subset Y$. In the context of this specific question think of $|Y| \approx 10000$.
We want to find function $f: Y \rightarrow \{0,1\}$ such that, $f(x) = 1 \iff x \in X$.
Now the worst I can do is basically do the interpolation which will grow quite fast. I think we could do better using the fact that this function has to be only defined on integers, not on real line. I want to find $f$ that is cheap to compute (preferably bitwise operations).
Obviously it very much depends on the nature of the $Y$. For example, if the set contains only odd/even integers then finding $f$ becomes trivial. How would I generally approach this problem? I thought about decomposing the set into arithmetic progressions and then checking for each of them, but that does not seem to be very promising approach.
Basically you are asking for a search routine.
They are not very cheap.
For repeated searches, pay the overhead of sorting X.
Yes, if X has a nonrandom structure such as even numbers only,
that structure can be taken advantage of for a quick search.
Being a factor of seven wouldn't be as quick.
Will your data be structure so a program could be written
that would be cheaper than a general search routine?