Topics About Contact Resources Quotes

How Efficient is a Binary Search?

Worst Case Number of Checks

# of linear search checks:
# of binary search checks:
A binary search performed fewer checks than a linear search

Why Is Binary Search so Efficient

A binary search is an efficient way to search big data sets because it halves the number of options after each guess.
No matter how big the data set is, if we continue to cut it in half with each guess we'll have only one option in short order. Try starting with any number and see how many times you can divide by 2 before get to 1.

When things decay be division instead of subtraction, they shrink fast. Likewise when thing grow by multiplication instead of addition they grow surprisingly fast, compound interest demonstrates this.

What Are the Disadvantages of a Binary Search

Everything has it's down sides and binary searches are no exception. The most significant disadvantage is that our data has to be sorted. In some instances sorting is not a problem, but sometimes it is a problem.

Why does the data have to be sorted?
Because after each check we eliminate everything on one side of our guess, based on if the thing we are looking for is more or less than our guess, we can not do this if things are not sorted.

For Binary Search, Bigger Is Better

Binary search shines with big data sets, the more items we have the more impactful binary search will be. If we don't have many items to search a binary search might not be worth implementing, but if we have a large data set and sorting is not an impediment then binary search is a great tool.

Resources