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?