linear search optimization - cutting number of calculations

Question

I'm wondering - is it possible to improve the linear search algorithm(on arrays, not lists), so that it'll do about half of the calculations?

for instance, this is the basic linear search algorithm:

i <- 1
while i<=length[a] && a[i]!=v
     do i <- i+1
if i>length[a]
     then return NIL
      else return i

now, if it was sorted we could've used binary sort or use the ceiling function to do about half of the calculations, as far as i understand. but if the algorithm the given array is not sorted - can we do about half of the calculations?

if i calculate it correctly, expected number of calculations is (n-1)(n+2)/2n while the worst case is n-1

is it possible to decrease the number of calculatios for about half of the amount?

note: using a sentinel might improve it a bit, but still won't decrease it to about half of the calculations

thank you very much for your help

Answer 1

First, n/2 is still O(n). Second, in case searched element is in an array and all numbers in the array are distinct (in case there are repetitions number of comparisons even smaller), then a number of comparisons:

1/(n-1)*1 + 1/(n-1)*2 +...+ 1/(n-1)*n-1 = 1/(n-1)*(1+2+...+n-1) = 1/n*(n*(n-1)/2) = (n-1)/2

but in case a searched element is not in an array, then instead of 1/n factor you need to use the number of distinct elements in the array divided by a number of all possible objects/numbers. If the ratio is very small, most likely you need to go all through the array to check if it is an array or not, so you need almost n comparisons. Here the analysis may be complicated if elements in an array drawn from the underlying universe not uniformly.