The Decision Tree

  • Illustrate the decision tree corresponding to the binary search process.

Consider the following ordered sequence of numbers:

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

Imagine we are searching for the value xx, and we perform a binary search. The following illustration shows the decision tree (or comparison 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 xx, we start the search by comparing it to the value of the element in the middle of the sequence, 99. If x=9x = 9 then the search ends. Otherwise, there are two possible outcomes:

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

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