Scan every ith entry of L for a fixed i. Suppose you have established that
then sequentially search 
.
because there are 
partitions, and there are (i-1)
items to search sequentially within a partition.
eg. i=4, W(n)=n/4+3
i=10,W(n)=n/10+9
i=100,W(n)=n/100+99
but still O(n) for fixed i.
How about i depending n?
eg. 
better than O(n) of seq search.
( 
)
eg. 
better than 
.
eg. 
Let us minimize for i,
W(n)=n/i+i-1
set to 0 and solve, gives .
Hence 
is the best
possible with the approach.