The Decision Tree

Consider the following ordered sequence of numbers:

$$ 2, 4, 5, 7, 8, 9, 12, 14, 17, 20, 21, 25 $$

Imagine we are searching for the value $x$ and we perform binary search. The following illustration shows the decision tree (or comparision tree or search tree) corresponding to the binary search process.

A decision tree is a flowchart-like structure that models the decisions (conditional statements in an algorithm) and their possible outcomes (consequences).

Irrespective of the value of $x$, we start the search by comparing the value of $x$ to the value of the element in the middle of the sequence, $9$. If $x = 9$ then the search ends. Otherwise, there are two possible outcomes:

  1. $x>9$ in which case we will explore the right half of the sequence (next comparison will be against $17$).
  2. $x<9$ in which case we will explore the left half of the sequence (next comparison will be against $5$)

This process is repeated until the search succeeds or fails (no more values left to compare).