Question

How many comparisons are needed for a binary search in a set of 64 elements?

Short answer

The number of comparisons needed is 14.

Step-by-step solution

Recurrence Relation definition

A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms:$\mathbf{\text{f(n) = a f(n / b) + c}}$

Apply the Recurrence Relation

Binary search divides each list into two sub-lists and determines in which sub-list the elements will need to be present (since the initial list is sorted).

Let$f\left(n\right)$ represent the number of comparisons in a set of $n$elements.

The binary search thus makes 2 comparisons in each step (to the two sub-lists), while the number of elements in the new list is half the number of elements of the original list:

$\text{f(n) = f(n / 2) + 2}$

Repeatedly apply the previous relationship with $n=64$:

$$\begin{gathered} f\left(64\right)=f\left(32\right)+2 \\ f\left(64\right)=f\left(16\right)+4 \\ f\left(64\right)=f\left(8\right)+6 \\ f\left(64\right)=f\left(4\right)+8 \\ f\left(64\right)=f\left(2\right)+10 \\ f\left(64\right)=f\left(1\right)+12 \\ f\left(64\right)=2+12 \\ f\left(64\right)=14 \end{gathered}$$

When the list contains 1 the element, then we require 2 comparisons.

Thus we require 14 comparisons