Decision tree for searching element in sorted-array

Question

Given the problem of having a sorted array $A$, an element $x$ to be searched for in the array $ A $, what is a lower-bound on the process of finding $x$ in $A$?

The answer is $ \Omega(\log n) $ because I was told that $ n $ is the number of leaves in the decision tree and so $ \log n $ will be the height of the tree.

First, without being aware of the fact that we are talking about a sorted array, I drew the tree for performing sequential-search on $A$,

But I got a height of $n$ and not $ \log n $.

Next, noticing the given array is sorted, I thought about drawing a decision tree for binary-search algorithm and I found the following link that draws the tree as I wanted, http://bcs.whfreeman.com/webpub/mathematics/gersting7e/chapter%206/section6-3/problem1/Page7.htm

( Here's an image in case you can't enter the link: )

But my teacher-assistant told me that when we want to show a lower-bound on process, we can show it by drawing a decision-tree for any algorithm that solves the process and not just a specific one. Meaning that we want to bound the decision tree's height for any algorithm that solves the specific problem.

That means, I was wrong in my analysis of having drawn both decision trees since I referred to two specific algorithms ( sequential search and binary search ) that solve the problem and not a general algorithm.

Question: So I wanted to know, how can one draw a decision tree for an arbitrary algorithm that solves the problem of finding $x$ in a sorted array $A$? ( It seems to me that the tree will be extremely algorithm dependent like in the two cases I've brought above and so I'm unable to seeing other wisely how the decision tree can be generalized not for specific algorithms )

Note: The question Doubt in the correctness of decision tree models for constructing a lower bound is similar to mine but not exactly what I asked for since I want to know how the decision tree should look like for any algorithm that solves the described problem.

Thanks in advance for help!

Answer 1

You haven't really defined your computation model, so here is a suggestion.

The input to the algorithm is a sorted array $A$ of length $n$ and an element $x$.

The output is either a position $i$ such that $A[i] = x$, or $\bot$, which means that $x$ is not in the array.

An algorithm is a decision tree whose leaves are labeled by outputs, and whose interior nodes are labelled by indices $i \in \{1,\ldots,n\}$, and have three children labeled $A[i] < x$, $A[i] = x$, $A[i] > x$.

An algorithm is legal if for any sorted array $A$ and for any $x$, if we traverse the decision tree then we get the correct answer (this can be formalized more carefully).

The running time of the algorithm is the depth of the decision tree (maximal number of edges in any root-to-leaf path).

Every legal algorithm has at least $n + 1$ different leaves, since for any array $A$ whose elements are distinct, we can find $n+1$ inputs for which the only correct outputs are $1,\ldots,n,\bot$.

Since every internal node has fan-out $3$, a decision tree of depth $d$ has at most $3^d$ leaves. Since $3^d \geq n + 1$, we conclude that $d \geq \log_3 (n+1)$.

This is achieved by binary search, up to a constant factor. With more work, we can show that binary search (probably defined) is strictly optimal. This requires an adversary argument.

Answer 2

The lower bound can be found as the minimum height of a binary tree holding $n$ leaves. A complete tree has this property and has a logarithmic height.