Proof on lower bound of search in unsorted array with information theory?
Here is an informal proof, which you can try to formalize.

Suppose that we’re looking for 1 in an array of length $n$ of 0s and 1s. We consider the following distribution: each element is 1 with probability $1/n$. (You can also try your luck with the uniform distribution over all arrays with a single 1.)

Given the transcript of the algorithm, you can either recover the position of a 1, or deduce that the array consists only of 0s. Since typically there are only few 1s, the entropy of the answer should be $\Theta(\log n)$.

On the other hand, each position you query only gives you $h(1/n) = \Theta(\log n/n)$ information. Hence you need to query $\Omega(n)$ bits.