The Binary Search Algorithm: Fast search times in sorted arrays

mgcadmin 24-09-2021

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

 

---