Is there a theorem that says when an array of numbers can be searched faster than linearly?

Question

I'm familiar with binary search, but I'm interested in when a collection of numbers can be searched faster than checking them all one by one with any algorithm. Binary search requires sorting to work, which means some knowledge of the structure of the collection, but maybe there is something else.

Answer 1

In general, if you know nothing about the array, then searching linearly is the best you can do (a simple adversarial argument is enough to justify this).

However, if you know more about the structure of the array, there are plenty of things you can do.

For example, imagine the array has the following property: its elements are sorted increasingly up to a certain index $i$, and sorted decreasingly after that. Can you do faster than a linear search? Yes! You can still search elements in $O(\lg n)$.

What if I ask you to search in an array $A$ that is sorted increasingly except for $1$ element, which is out of place? (you don't know which element). You can still search in $O(\lg n)$, how :)?

What if the array $A$ holds the following property: when you divide it in chunks of size $\sqrt{n}$, say $A[0..\sqrt{n}-1], A[\sqrt{n}..2\sqrt{n}-1], \ldots, A[n-\sqrt{n}..n-1]$, then each of the chunks is sorted. Can you do faster than a linear search? Yes! if you do a binary search in each chunk, then you get complexity $O(\sqrt{n}\lg n)$.

What if you know the array $A$ has only two elements, $x$ and $y$, and they both appear the same number of times? Can you find an element in less than $n$ comparisons? Yes!

In general, there are many different kinds of informations you can have about an array that speed up search, and different forms of knowledge would have different impacts on how much you can speed up.