The problem is as follows. Given a set $S$ of natural numbers of size $n$ where each $x\_i \in S$ is from the set $[n^2]$. Elements of $S$ are not necessarily pairwise different, i.e., there can be duplicates in $S$. Given an input number $y \in [n^2]$, find the first occurrence of $y$ in $S$, if any. That is, suppose $S$ is an array of numbers, find minimum $i$ such that $x\_i = y$, if any.


A naive brute force algorithm would take $O(n)$ time. The question is can we do that in sub-linear time in expectation by, e.g., a Las Vegas algorithm?



Randomized algorithm?
You can't do that. Most probably $y$ does not occur in $S$ at all, and when it does it will most probably occur only once. In either case you cannot hope to know that fact, or locate $y$, without looking at all elements/half the elements on average.


