The Binary Search Algorithm: Fast search times in sorted arrays
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) {
if (r >= l) {
int m = (l + r) / 2;
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:
int binarySearch(int t[], int l, int r, int val) {
while (l <= r)
{
m = (l+r) / 2;
if (val == t[m]) return m;
if ( val < t[m]) r = m - 1;
else l = m + 1;
}
return -1;
}
Performance Matters
So how much faster is binary search anyway? Well, theres some conjecture that on modern computer architectures, it's not. However, if we are strictly going by the number of comparisons, well its not even close:
Searching For: 18349 Running Binary Search... Found! Items Searched: 5 Running Sequential Search... Found! Items Searched: 9218
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
-
A Different Take on Merge Sort: Binary Search Trees?
-
Deleting Entries From Open-Address Hash tables
-
Transform any Binary Search Tree in to a Sorted Linked List
-
From Regular Expressions To NFA by way of Abstract Syntax Trees: Thompsons Construction
-
Extending Sedgewick's explicit Digraph NFA
-
Iterative In-order B Tree Traversal
-
Simple DB Migration with JDBC
-
Welcome to CodeBlahger, A Blahging Platform for Programmers.
-
The Façade Pattern
-
The Interpreter Pattern: Implementing Interpreters the OOP way
Leave A Comment