WTF: is Binary Search?

Hi, welcome to another WTF: is *Blank*, today we’re going to be discussing what Binary Search is. There are multiple ways of searching a specific element (an integer, or string etc.) in a given array and one of those ways is binary search, which essentially cuts the array as we loop through it. So let’s get started!

Introduction:

Binary search is one of the basic search algorithms you learn when studying programming. It essentially breaks the part of the array we don’t need to loop through as we go on, so at the end of the search we are left with our desired output. One thing to keep in mind about binary search is that it only works on sorted arrays. Now that that’s out of the way, let’s learn how to implement binary search, I’ll be using JavaScript but you can code it in any other language as the concept remains the same.

Implementation:

First, our function will take two arguments, the input array ‘arr’ which is to be searched and the element ‘target’ we need to find in the input array.

Now, let’s make three variables, start, middle, and end which will act as pointers (indicators) for the first, middle and last element of the array, respectively.

The start pointer can be indicated as index 0 of the array, while the end pointer can be one less than the array’s length which ends up being the last element. For the middle pointer, we can find the average of the start and end pointer and convert it to an integer (in case it ends up being a float).

Now that we have our pointers, let’s write the fun stuff;

We’ll start off by writing a loop which compares our arr[middle] value in the array to our target value, if we’re lucky enough we might get our target value without running the loop. Anyways, if arr[middle] is not our target value, we check to see if that middle value is greater or lesser than our target.

In the case, our middle value is greater, we switch our end pointer to be one less than our middle ( end = middle - 1 ), because we now know that our target is somewhere in those elements. The same goes for when our middle value is less than our target, then we switch our start pointer to be one more than our middle value ( start = middle + 1).

Now, because we have a new start or end index, we now need a new middle index, so we repeat the same thing as we did before: take the average of start and end pointer then round it off to the nearest integer. At the end of the loop, we keep checking if our middle value is equal to our target value which, if true, will return us the middle index, otherwise it will keep on looping.

But what happens if the target value is not in the array? Well, our current program will keep on looping till infinity, so to tackle that we just need to add another condition in our while loop;

In the while loop, we check if our start pointer is lesser than or equal to our end pointer, because in the case that statement is false, it means our loop has went outside the array resulting in the target value not being present, and the same goes if the end pointer is less than the start pointer.

And there you have it, we have implemented a simple binary search algorithm.

Hey there! Thanks for reaching the end of this post, if you liked it or have any questions, feel free to comment!