pick a random number not in a list

Question

I have a list:

> S = [1,8,93,3,8]

I need to pick a random number that is not in the list but within the max range of value. I am more concerned about time complexity O(n). The S could be a pretty big list.

import random

S=[1,8,93,3,8]
m = max(S)
for x in xrange(m):
  rand = random.randint(1,m)
  if rand not in S:
      print rand
  else:
      print "Number - %d found in the array" % rand 
      break

I did not try list comprehension

Answer 1

Just ripped something out of a project of mine

while True: 
    self.uid = random.randint(0,100000)
    if not(self.uid in item_uids):
        break

Sketchy solution but it works.

Answer 2

If the list consists of integers and any number is acceptable:

S = [1,8,93,3,8]
number = 0.5

If the number must be an integer:

S = [1,8,93,3,8]
number = max(S) + 1

If the number must be an arbitrary integer between the largest and smallest elements in the list:

S = [1,8,93,3,8]
number = next(iter(set(range(min(S)+1, max(S))) - set(S)))

If the number must be a psuedorandom integer between the largest and smallest elements in the list:

import random
S = [1,8,93,3,8]
number = random.choice(list(set(range(min(S)+1, max(S)))-set(S)))

Answer 3

This is the simplest thing I could come up with:

import random

S=[1,8,93,3,8]
m = max(S)

not_in_S = random.choice([x for x in range(m) if x not in S])