Visualizing a Binary Search

The binary search algorithm can be a great tool to search for a value in a sorted data structure, in this case it will be an array. (Important Note: The array has be sorted for this to work.) What’s great about implementing a binary search is that we can find our value in O(log n) time complexity versus O(n). We’ll be taking a look at solving LeetCode’s Binary Search with both time complexities to see how much of a difference there is.

Big-O Cheat Sheet

The problem on LeetCode states:

“Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.”

An example input and output is :

Input: nums = [-7, -1, 2, 11, 19, 20, 24, 27, 35, 39], target = 20
Output: 5
Explanation: 20 exists in nums and its index is 5

Of course, we can solve this with a simple loop.

This is a perfectly fine answer. Our target number, 20, is the 5th index in the array, so we would have looped through our loop six times to get to 20. However, whenever a problem is given, there is almost always a clue that can lead us to a more optimal solution. In this problem, the clue is “sorted.” This should set off a light in your head that we can implement a binary search.

We’ll start with defining a few variables. Initially, we will be pointing at the starting index of our nums array with the left variable and the ending index of our nums array with the right variable. We will initiate the middle variable but not define it just yet. It will be redefined in each iteration of our while loop.

As long as left is less than or equal to right, we will enter the loop. Inside of our while loop, we will start with finding the middle index of our nums array and assigning it to middle. We then have 3 possible scenarios:

1. If the middle index of our nums array is equal to our target number, we have found our solution and we can return middle.
2. If the middle index is greater than our target number, we can rule the middle index out. And since our nums array is sorted, we know we can also rule out every index to right of it. We will then reassign right to the index before the middle index and start our loop again.
3. The only option remaining is that our middle index is less than our target number. We can rule out the middle index. And again, since our nums array is sorted, we can rule out every index to the left of our middle index. We will reassign left to the index after the middle index and start our loop again.

Once the left points to an index further than the index right points to, we will have broken out of the loop. This means that we never found the target number in our nums array and we will return -1.

Now, we’ll take a look at a visualization of what is going on in our binary search:

The first time we enter our while loop, left is pointing to the first index, 0, and right is pointing at the final index, 9. We will determine middle by getting the average and rounding down. This will give us 4.

Our middle index points to 19, which is less than our target number, 20. So we know that every number to the left of 19 is also less than our target number, 20, and they can be ruled out. We will then reassign left to middle + 1.

This is the second time through our loop and we have already ruled out half the nums array. Left now points to the 5th index and right still points to the 9th index. We can now re-determine middle by getting the average, which will give us 7.

Our middle index points to 27, which is greater than our target number, 20. The same concept applies as the previous loop. We know that every number to the right of 27 is also larger than our target number, 20, so they can also be ruled out. We will then reassign right to middle - 1.

This is just the 3rd time through our loop and most of the array has been ruled out by this point. Left still points to the 5th index and right now points to the 6th index. We re-determine middle by getting the average and rounding down, which is 5.

Our middle index now points to 20, which is our target number. We can now return 5!

When comparing both solutions, we’ll see how much quicker a binary search can be in comparison to just a normal iterative search. In our particular example, the iterative search looped 6 times as opposed to the binary search, which only looped 3 times to find our target number. Of course with this size of array, it does not make all that much of a difference. However, we can see how this could really add up over time when we get to arrays that are thousands or more numbers long.

Worst case scenario for our iterative solution is that the target number number is the last number in our array. This would mean that we would loop through the array n ( the length of the array) number of times and the time complexity of the iterative solution is O(n).

Determining the worst case scenario for our binary search solution is a little more complex (no pun intended?). You can read an in-depth explanation of it here. But this is the gist of it: Because each time we go through our while loop we could rule more than 1 number out in our array, even in the worst case, we would not have to loop through every number in our array. The time complexity is O(log n).

Thanks so much for reading! If you have any questions or comments, feel free to leave them below!

You can find me on Twitter at @a_cisneros45.