A Common-Sense Guide to Data Structures and Algorithms

An Algorithm of the Third Kind

In the previous chapter, we learned that binary search on an ordered array is much faster than linear search on the same array. Let’s learn how to describe binary search in terms of Big O Notation.

We can’t describe binary search as being O(1), because the number of steps increases as the data increases. It also doesn’t fit into the category of O(N), since the number of steps is much fewer than the number of elements that it searches. As we’ve seen, binary search takes only seven steps for an array containing one hundred elements.

Binary search seems to fall somewhere in between O(1) and O(N).

In Big O, we describe binary search as having a time complexity of:

O(log N)

I pronounce this as “Oh of log N.” This type ...