The binary search algorithm allows use to search for an item in a sorted array with much faster results than performing a search linearly.
A need arises
Searching is a fundamental task in computing, and arguably the most frequent task performed by computers. Whether a user is looking for friends on social media, a file you saved on your computer, or for a particular video on you tube, providing an efficient way to locate the data one is looking for remains an important need for software developers. In this article we will discuss one of the foundational searching algorithms for array based data: the Binary Search Algorithm.
The most straight forward searching algorithm, sequential search, works by going through every single element in an array and comparing it to the item your searching for, either stopping when it encounters that item, or continuing to the end before reporting failure.
bool sequentialSearch(int val, int t[], int size)
{
int i;
for (i = 0; i < size; i++)
{
if (t[i] == val)
{
return true;
}
}
return false;
}
Needless to say, on a large data set this consumes an unacceptable amount of both time and resources. If the data in the array is arranged in sorted order then we can use whats called Binary Search to drastically reduce the number of comparisons required to determine if the element we are searching for exists or not.
A better way
If you were looking for the term segmentation fault in a dictionary of programming topics, you wouldn’t start with the A’s and go through every single word until you found segmentation fault. More likely, you’d open up the book to somewhere near the middle, and if you the page you opened to was before the “S” section, youd keep flipping the pages foward, and if was after S, youd keep flipping pages backward. This is the idea behind Binary Search. After each iteration of the algorithm, the amount of data we need to search through is cut roughly in half.
The drawback to Binary Search is that it only works if our the array were searching is ordered. Thankfully there are an abundance of sorting algorithms to take care of that for us.
The Algorithm
Binary Search in itself is very easy to implement either iteratively, or if one desires recursively. I’ll demonstrate both methods. Up first: Recursive Binary Search.
bool binarySearchR(int val, int t[], int l, int r)
{
int m = (l + r) / 2;
if (r >= l)
{
if (val == t[m])
return true;
if (val < t[m]) return binarySearchR(val, t, l, m-1);
else return binarySearchR(val, t, m+1, r);
}
return false;
}
If you’ve ever implemented a Binary Search Tree than this algorithm should look familiar: Its where binary search tree’s got their name from.
If the array your searching is large, an iterative solution will be more efficient. Binary search can be implemented using a while loop with only slight modification to the above code:
bool binarySearch(int val, int t[], int size)
{
int l = 0;
int r = size;
int m = (l+r) / 2;
while (r >= l)
{
m = (l+r) / 2;
if (val == t[m]) return 1;
if ( val < t[m]) r = m - 1;
else l = m + 1;
}
return 0;
}
Performance Matters
I’ve been saying throughout the article that Binary Search is far superior to Sequential Search when searching through large data sets. To test this, i wrote a program to generate 10,000 random numbers and store them in an array. The 42nd random number generated is saved in a variable and is used as the number we are going to search for. After sorting the array using selection sort, it is run through both binary search and sequential search, keeping track of the number of comparisons before we find the number were searching for.
So how’d it turn out?
Searching For: 18349 Running Binary Search... Found! Items Searched: 5 Running Sequential Search... Found! Items Searched: 9218
WOW! That is QUITE a difference. It goes without saying, if when searching an array, if the data can be sorted into ascending order before the search, than binary search is leaps and bounds ahead of sequential search when it comes to finding the item we are looking for.
All of the source code for the examples shown in this article are available at my github:
https://github.com/maxgoren/examples/blob/main/binarysearch.c
