Space complexity for finding the minimum number outside the list of numbers

We are given an (unsorted) list $L=(a_1,\dots,a_n)$ of numbers of size $n$, where $a_i\in \{ 1,\dots,B\}$.

We want to find the minimum number $x$ from $\{ 1,\dots,B\} \backslash L$.


What is the space complexity of this problem ? (The space to store the input, $L$, does not count.) What if the input $L$ is in a stream which you can only read from left to right for at most constant number of passes ?

The obvious way to solve this is just to copy $L$ into the working memory and then (in-place) sort $L$, and find $x$ in the obvious way. This algorithm uses space of size $n$.

Can we do better ?

You can solve this in time $O(n\log B)$ and constant space (assuming a machine word can store numbers up to $\max(n,B)$) using binary search.

Edit: Here are some more details. I am making the assumption that no number appears twice - perhaps that's an unfounded assumption. Given $K$, we can check whether $KL$ by counting how many numbers smaller than $K$ appear in the input, and whether $K$ itself appears in the input. This takes $O(n)$.

Edit 2: Following eig's suggestion, since we know that the missing number is smaller than $n+2$, this actually takes time $O(n\log n)$.

StackExchange Computer Science Q#11174, answer score: 4