Establishing a lower bound for searching

Today, we are going to establish a lower bound for searching and prove that binary search is optimal, and no comparison based search in this universe would be better than that by more than a constant factor. Let’s define our problem more formally first.

Theorem

Let us assume that we have $n$ pre-processed items in the array. Finding a given item among them in a comparison model requires $\Omega(log_2 n)$ in the worst case.

Computation Model

Let’s try to model the situation using a decision tree. In this decision tree, an internal node represents a decision that our algorithm makes and a leaf represents an answer. Here’s our representation of the problem using a decision tree computation model for $n = 3$ element array for the sake of simplicity.

I mentioned here that the Items are preprocessed to mean you could do whatever you want with items ahead of time. For instance, I can sort them, build them into an AVL tree et.al.

Proof

Let $n$ be the number of items in the input array. Then, we have at least $n + 1$ leaves in our binary tree. Since a binary tree of height $h$ has no more than $2^h$ leaves, we have

$n + 1 \le 2^h$

By taking logarithms on both sides we then obtain:

$log_2 (n + 1) \le h = \;$worst case running time

$\Omega(log_2 n) = h = \;$worst case running time

Corollary

Binary search is asymptotically optimal comparison search.

References

[1] https://www.amazon.com/Introduction-Algorithms-fourth-Thomas-Cormen/dp/026204630X