as we are given the numbers to be chosen , choose any consecutive 5000 integers or 5000 integers with constant difference then map it on to a array of size 5000. Store the numbers in the set by arr[no in set ]=1; Then you can store them in an array and the above operation can be done in o(1).
When the range of number is not given, then you have to sort them (prepocessing) and then do a binary search . This is efficient i think.
