An Introduction to the Binary Search

If you're here, you probably searched "how does the binary search work," or "how to write binary search." I will be teaching just that, along with the theory and some visuals along the way.

Some Background Before the Code:

Before we dive into the binary search itself, it is important to understand why it is a much faster search than a linear search. For starters, the linear search, by definition, is linear time complexity. This means that in the best possible case, the first element is what you search for. In that case, the time is incredibly low, however, the element could also be at the last position, meaning the time is incredibly high. 

A binary search on the other hand has logarithmic time complexity, meaning it could still have that incredibly low time if the element it starts at is the target, but the average time is also quite low. 

Above is a time complexity graph with the input size on the x-axis and the time taken on the y-axis. The blue is for a binary search while the red represents the linear search. As is obvious, the binary search is vastly more efficient.

Another note is that a binary search can only be used for an ordered list, and will be completely useless if the list is unordered, so keep that in mind when implementing it.

Still Not Time to Code, But Here's the Theory:

A binary search searches through a list by keeping track of a left, right, and middle pointer. The middle pointer is the one that checks the value, and the other two pointers hold the high and low bounds of where the value can be. Here are the steps to the binary search:

1. To begin, everything is within a while loop that is conditional on the left pointer being less than the right pointer.
2. The middle point is established by finding the mean of the left and right pointer.
3. The value of the middle point is checked if it is equal to the target value.
4. If it is equal, the middle point value is returned, which is also the index of the target.
5. If the middle point value is greater than the target, the right pointer is moved to the middle point -1, because the target has to be below that point.
6. If the middle point value is less than the target, the left pointer is moved to the middle point +1, because the target has to be below that point.

Some more things to understand: the left pointer always starts at 0 (assuming a 0-indexed list), and the right pointer is set to the length of the list -1 (this also assumes a 0 indexed list). Additionally, it may be helpful to return -1 at the end of the code, outside of the while loop of course. That will show you that there is not an item with the same value as the target within the list.

Now We Can Get Into Some Coding:

Please note that all of these programs are tailored to the Leetcode binary search problem. Also, the name of the array in all of the examples is nums.

Personally, I think Python3 is the easiest to understand when it comes to a binary search, so that will be the first example:

For the second example, I'll give a Java program:

Finally, here is a program in C++:

That's all! I really hope you learned something from this and good luck in your coding endeavors!

Also, feel free to leave a comment about any computer science topic you would like an article on.