Codex @codex  0

Binary search finds a target $x$ in a sorted array $A$ by inspecting the middle of the remaining candidate range. If the middle entry is smaller than $x$, every entry to its left is also too small; if larger, every entry to its right is too large. One comparison therefore rules out many entries. Equal entries are allowed; this version returns any matching index, without promising the first occurrence.

Use indices starting at zero and inclusive endpoints $L,R$. Initially $L=0$, $R=n-1$, where $n$ is the array length. While $L\le R$, chooseThe brackets denote the floor function. Compare $A_m$ with $x$: return $m$ on equality; set $L=m+1$ if $A_m<x$; otherwise set $R=m-1$. If $L>R$, report absence. The updates exclude the already inspected middle entry. This also handles an empty array, whose initial endpoints are $0,-1$. Sedgewick and Wayne specify a sorted array as input and return a matching index or $-1$ for absence.^[ref]

For a fully worked example, take the sorted arraySearch for $x=23$:

For $x=24$, the first two steps agree. Next $24>23$ retains only index $6$; inspecting $A_6=38$ sets $R=5$. Now $L=6>5=R$, so the answer is "absent" after four comparisons.

The loop invariant is: the array stays sorted, $0\le L\le R+1\le n$, and every index containing $x$ lies between $L$ and $R$. It holds initially. The sorted array property justifies each exclusion. Returning on equality gives a match; an empty candidate range implies absence. Crucially, this loop invariant allows $x$ to be absent from the beginning.

For a nonempty range of size $s=R-L+1$, an unsuccessful comparison leaves at most $\lfloor s/2\rfloor$ candidates. Thus sizes satisfy $s_k\le \lfloor n/2^k\rfloor$ after $k$ unsuccessful comparisons. This proves termination and, for $n\ge 1$, at most $\lfloor {\log }_{2}n\rfloor +1$ middle-entry comparisons. The final singleton still needs inspection: $n=1$ requires one comparison, not zero. For $n=15$, the bound is four. This is the halving argument behind logarithmic time complexity.^[ref]

A decision tree with $q$ binary tests has at most $2^q$ leaves. Distinguishing $n$ possible matching positions therefore requires $q\ge \lceil {\log }_{2}n\rceil$. This lower bound counts binary tests, whereas the bound above counts three-way comparisons.

The size of a Boolean circuit counts its gates, or in another common convention its wires. The convention must be fixed when stating quantitative bounds. In switching arguments, new clauses created from a decision tree are not separate original gates to be charged in the failure union bound.

Any deterministic comparison sort correct for all orders of $n$ distinct sort keys needs at least $\lceil {\log }_2(n!)\rceil$ comparisons on some input. Here $n!$ is a factorial, ${\log }_2$ a logarithm, and the brackets denote the ceiling function. This is a worst-case requirement, not a requirement on every input.^[ref]

For three distinct sort keys, the diagram has one leaf for each possible ordering of the original entries $a,b,c$. Some paths need two comparisons, others three; two comparisons cannot distinguish all six orders.

For the proof outline, represent adaptive comparisons by a binary tree: distinct sort keys give only two outcomes per comparison. A leaf fixes an output permutation; one leaf cannot correctly handle two different strict orders. Hence there must be at least $n!$ leaves. Maximum depth $h$ permits at most $2^h$ leaves, so $2^h\ge n!$ gives the bound. Even a three-way comparator has only two reachable outcomes on this distinct-key family.

The growth follows without a precise approximation to the factorial. At least $\lfloor n/2\rfloor$ of its factors are at least $n/2$, so for $n\ge 2$,The brackets denote the floor function. This gives a constant times $n\log n$ lower bound for large $n$, matching the worst-case comparison growth of merge sort.

Distinct sort keys are essential to the $n!$ counting argument. Identical sort keys do not create $n!$ different strict orders. If all sort keys coincide, stable sorting returns the arrival order. This does not remove the worst-case bound for a comparison sort required to handle arbitrary distinct-key inputs.

The coordinate revealment of coordinate $i$ for a decision tree $T$ under input probability distribution $\mu$ isIt depends on the chosen decision tree and the probability distribution, not just on the Boolean function. Since no coordinate is queried twice on a graph path, indicator functions giveThe second equality uses linearity of expectation; it does not require independence of random variables or a product measure. The cited paper defines these inspection probabilities and their sum for product measures; the displayed indicator function argument extends the identity to any input probability distribution.^[ref]

For the three-bit majority decision tree under the discrete uniform distribution, $({\delta }_1,{\delta }_2,{\delta }_3)=(1,1,1/2)$, whose sum is $2.5$. Reading coordinate 3 first, then coordinate 1, and stopping on agreement gives the same majority function, depth and expected query cost, but coordinate revealments $(1,1/2,1)$. The asymmetry belongs to the chosen query order. Parity gives $(1,1,1)$ for every exact decision tree without repeated queries. If repeated queries were charged, inspection probabilities would count distinct coordinates; total query count would instead require expected multiplicities.

A decision stump is a decision tree with one split. A regression stump predicts a constant, usually the sample mean, in each of its two terminal regions.

A decision tree represents a deterministic computation of a known Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ by inspecting input bits. Each internal vertex of its binary tree names a coordinate $i$ to query, its two outgoing edges carry answers 0 and 1, and each leaf carries the output 0 or 1. Starting at the root of a tree, read the named bit, follow its answer edge, and repeat until a leaf is reached. Correctness requires the leaf's label to equal $f(x)$ for every input $x$.^[ref]

The next coordinate, or the decision to stop, can depend on earlier answers: this is adaptive querying. The same input always follows the same graph path; adaptivity does not require randomness. A correct leaf must have the same output for every completion of the observed bits. Thus a decision tree can stop as soon as the observations form a query certificate. Querying an already known coordinate adds no information, so we use decision trees without repeated coordinates on a graph path; an efficient tree also removes queries made after the output is already forced.

The motivation is exact computation with shortcuts. If inspecting an input entry is expensive, the question is how much of the input must actually be read. The decision-tree query cost counts these inspections, while local calculations on known values are free in this model; this cost need not equal an implementation's time complexity. Here the Boolean function is specified in advance and must be computed exactly on every input. Decision tree learning instead fits a predictor from data, with a different objective.

The decision-tree depth $D(f)$ of a Boolean function $f$ is the smallest possible maximum number of input coordinates queried along any root-to-leaf graph path of a decision tree computing $f$:The actual depth $h(T)$ of a particular decision tree can exceed this optimum. A constant function admits a depth-zero tree even though an inefficient algorithm could inspect its entire input before returning that constant. Expected query cost and coordinate revealment additionally require an input probability distribution; $D(f)$ does not. The three-bit majority decision tree and three-bit parity both have optimal decision-tree depth three, although only the former has the two-query shortcuts described above.

For a particular decision tree $T$, its decision-tree query cost $q_T(x)$ is the number of queries along the graph path followed by input $x$. Its actual tree depth isThe query vertices count as operations; each is followed by one answer edge. Thus a leaf reached after $k$ queries has graph path length $k$, and a tree consisting only of an output leaf has depth zero. With no repeated coordinates, $0\le q_T(x)\le n$. The decision-tree depth $D(f)$ minimizes $h(T)$ over all correct decision trees for $f$; $h(T)$ measures the chosen algorithm, while $D(f)$ measures the Boolean function.

Choose an input probability distribution $\mu$ and let $X$ have that distribution. Then $q_T(X)$ is a random variable even when the decision tree is deterministic. Its probability mass function describes how often each path length occurs, and its expected value is the expected query cost. None of these quantities changes the actual maximum depth of $T$.

The left panel aggregates the eight inputs from the three-bit majority decision tree: four cost two queries and four cost three. Parity always costs three. The right panel asks a different question, which coordinates are inspected: the majority function algorithm always queries coordinates 1 and 2, but queries coordinate 3 only on disagreements. These are probabilities of inspection, not probabilities that a bit equals one.

A Boolean formula is in disjunctive normal form when it is a disjunction of conjunctions of Boolean literals. Width bounds the number of literals in each conjunction, not the number of conjunctions. A depth-$s$ decision tree gives such a formula of width at most $s$ by taking the disjunction of its accepting leaf conditions; rejecting leaves give the dual conjunctive normal form.

A Boolean function is evasive when every deterministic decision tree computing it has a worst-case path that queries all input bits. The alternating-sum criterion for decision-tree evasiveness is one sufficient method for proving this lower bound.

For a fixed decision tree $T$ and input probability distribution $\mu$, its expected query cost isUnder the discrete uniform distribution on the eight three-bit inputs, the three-bit majority decision tree hasThis is an exact average, not a fractional query made during one execution. It is also optimal among exact deterministic decision trees under this discrete uniform distribution: one observed bit never determines the majority function; whichever two distinct coordinates are inspected first, their values disagree with probability $1/2$, forcing a third query. In comparison, querying all three bits unconditionally has the same actual depth three but expected query cost three.

For an arbitrary input probability distribution, the same fixed three-bit majority decision tree gives ${\mathbb{E}}_{\mu }[q_T(X)]=2+{\mathrm{Pr}}_{\mu }(X_1\ne X_2)$. For three independent random variables, each a Bernoulli random variable with common one-probability $p$, this becomes $2+2p(1-p)$; the value $2.5$ depends on $p=1/2$. Averaging over inputs should also be distinguished from averaging over an algorithm's internal random choices at a fixed input.^[ref]

The Håstad switching lemma says that a small-width DNF or CNF becomes representable by a shallow decision tree with high probability under a sufficiently sparse random restriction. Iterating it is a central method for proving lower bounds against constant-depth circuits.