Number of comparison operations done in a binary search

From Problemania
Jump to: navigation, search

Metadata

  • Classification trails: ComputerScience`DiscreteMathematics

Background

Prerequisite

Problem statement

Find the maximum, minimum, and average number of comparison operations done in computer program searching for a key in an array of size $N$ using binary search algorithm.

Hint

Solution

Answer

The maximum, minimum, and average number of comparison operations (a = b) done in a program searching for a key in an array of size $N > 1$ using binary search are

  • $\lfloor \log_2 N \rfloor + 1$,
  • $1$ (iff $N = 1$),
  • $\lfloor \log_2 \left( N /2 \right) \rfloor + 1$

respectively.

Discussion

Related pages

External links

References

Tags