Binary search is a search algorithm. It takes as input a value that we will call a “needle” and an array that we will call a “haystack” that is known to be sorted in, say, increasing order of values.
It determines if the needle is in the haystack or not. Furthermore, if the needle does occur in the haystack, it also returns the position in the array at which it can be found.
Example 1:
Input:
needle = 7
haystack = 1 3 4 5 7 8 9
Output:
4
0 1 2 3 4 5 6
haystack = 1 3 4 5 7 8 9
^
at position 4Example 2:
Input:
needle = 7
haystack = 1 3 4 5 6 8
Output:
-1 (needle does not occur in haystack)Why study binary search?
Binary search is an important algorithm to study and truly understand because of several features:
- Binary search is very efficient, and is one of the possible go-to algorithms for searches that need to be really fast;
- It is a foundational algorithm that is pedagogically important; it is one of the canonical O(log n) algorithms;
- Even if you never need to implement binary search yourself as a software developer, and instead merely use it in the form of database indices or using the C++ STL upper_range/lower_range functions, understanding how it works exactly under the hood could give you an edge;
- Binary search could also help you in real life, such as when you look up words in a dictionary :P;
- The algorithm is practically useful, and variations such as bisection search are used everyday in software development practice.
Go to the next page for an overview of the algorithm.
- Page 1 – Introduction
- Page 2 – How It Works – Overview
- Page 3 – Example 1
- Page 4 – Example 2
- Page 5 – Why Binary Search is so Fast
- Page 6 – Implementation
- Page 7 – Conclusion