Efficient search in a permutation

Question

Let $S$ be an array of length $n$ containing a random permutation of numbers from $0$ to $n-1$. What is the most efficient (in expectation) algorithm for finding the location of a given number $k$ in $S$? In other words, finding index $i$, such that $S[i]=k$.

---

I watched a video about a related puzzle and it seems that in expectation we can do better than a linear search. The idea is to search $S[k]$ then $S[S[k]]$ then $S[S[S[k]]]$ and so on. I think this will find the required index faster than checking every element (on average), but I am not sure.

I wrote some Java code to simulate this algorithm and here are the results for $n=3$. I show every possible permutation and the number of steps required to find every possible $k$. Each element of the permutation is written in the form "index:value".

0:0 1:1 2:2
0 found in 1 steps
1 found in 1 steps
2 found in 1 steps
maximum steps for this permutation 1

0:0 1:2 2:1
0 found in 1 steps
1 found in 2 steps
2 found in 2 steps
maximum steps for this permutation 2

0:1 1:0 2:2
0 found in 2 steps
1 found in 2 steps
2 found in 1 steps
maximum steps for this permutation 2

0:1 1:2 2:0
0 found in 3 steps
1 found in 3 steps
2 found in 3 steps
maximum steps for this permutation 3

0:2 1:0 2:1
0 found in 3 steps
1 found in 3 steps
2 found in 3 steps
maximum steps for this permutation 3

0:2 1:1 2:0
0 found in 2 steps
1 found in 1 steps
2 found in 2 steps
maximum steps for this permutation 2

average of maximum steps for all permutations 2.1666666666666665

This algorithm has an average for all permutations of 2.17 steps. Meanwhile the linear algorithm of checking every element will always have an element that requires the maximum steps of 3, so its average over all permutations will be 3, which is worse.

As $n$ increases the number of steps required by the above algorithm seems to approach $2n/3$.

But can we do better?

Answer 1

Linear search.

Reading values from $S$ give you no information on where $k$ can be and you can't avoid exhaustive search. If the permutations are equiprobable, whatever the order in which you try the locations, the distribution of the number of trials is uniform. The expectation of the number of comparisons is $\dfrac{n-1}2$ (best case $1$, worst $n-1$).

Note that knowing the particular values (naturals $1$ to $n$) helps in no way.

---

Update:

The correct value of the expectation is

$$\frac{n^2+n-2}{2n},$$ my bad.

Answer 2

Lets take a smaller example. Consider you have $10$ positions $[0, 1, 2, ..9]$ and the numbers are distributed as position $i$ has the number $(i + 1)mod10$. Now pick any $k$, it's easy to see that you'll have to traverse all the positions. So asymptotically, you have no benefit.

As far as expectation is concerned @Yves Daoust's answer gives you why it's unaffected. Also, implementing such a strategy in code isn't particularly helpful, it will only obfuscate the code, may make it harder for the compiler to optimize and may invalidate cache benefits if you are dealing with extremely large arrays.