In this article, we are going to help you understand the general concept of Binary Search.
What is Binary Search?
Binary Search is one of the most fundamental and useful algorithms in Computer Science. It describes the process of searching for a specific value in an ordered collection.
Terminology used in Binary Search:
- Target - the value that you are searching for
- Index - the current location that you are searching
- Left, Right - the indicies from which we use to maintain our search Space
- Mid - the index that we use to apply a condition to determine if we should search left or right
Other Binary Search Defintions:
How does it work?
In its simplest form, Binary Search operates on a contiguous sequence with a specified left and right index. This is called the Search Space. Binary Search maintains the left, right, and middle indicies of the search space and compares the search target or applies the search condition to the middle value of the collection; if the condition is unsatisfied or values unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. If the search ends with an empty half, the condition cannot be fulfilled and target is not found.
In the following chapters, we will review how to identify Binary Search problems, reasons why we use Binary Search, and the 3 different Binary Search templates that you might be previously unaware of. Since Binary Search is a common interview topic, we will also categorize practice problems to different templates so you can practice using each.
Note: Binary Search can take many alternate forms and might not always be as straight forward as searching for a specific value. Sometimes you will have to applying a specific condition or rule to determine which side (left or right) to search next. We will provide examples in sections below.
How do we identify Binary Search?
As mentioned in earlier, Binary Search is an algorithm that divides the search space in 2 after every comparison. Binary Search should be considered every time you need to search for an index or element in a collection. If the collection is unordered, we can always sort it first before applying Binary Search.
3 Parts of a Successful Binary Search
Binary Search is generally composed of 3 main sections:
Pre-processing - Sort if collection is unsorted.
Binary Search - Using a loop or recursion to divide search space in half after each comparison.
Post-processing - Determine viable candidates in the remaining space.
3 Templates for Binary Search
When I first learned Binary Search, I struggled. I studied hundreds of Binary Search problems online and each time I looked at a developer's code, it seemed to be implemented slightly differently. I was perplexed. Although each implementation divided the problem space in 1/2 at each step, I had numerous questions:
Why was it implemented slightly differently?
What was the developer thinking?
Which way was easier?
Which way is better?
After many failed attempts and lots of hair-pulling, I found 3 main templates for Binary Search. To prevent hair-pulling and to make it easier for new developers to learn and understand, I have provided them below:
99% of binary search problems that you see online will fall into 1 of these 3 templates. Some problems can be implemented using multiple templates, but as you practice more, you will notice that some templates are more suited for certain problems than others.
Note: The templates and their differences have been colored coded below.
These 3 templates differ by their:
- left, mid, right index assignments
- loop or recursive termination condition
- necessity of post-processing
Template 1 and 3 are the most commonly used and almost all binary search problems can be easily implemented in one of them. Template 2 is a bit more advanced and used for certain types of problems.
Each of these 3 provided templates provide a specific use case:
Template #1 (left <= right):
- Most basic and elementary form of Binary Search
- Search Condition can be determined without comparing to the element's neighbors (or use specific elements around it)
- No post-processing required because at each step, you are checking to see if the element has been found. If you reach the end, then you know the element is not found
Template #2 (left < right):
- An advanced way to implement Binary Search.
- Search Condition needs to access element's immediate right neighbor
- Use element's right neighbor to determine if condition is met and decide whether to go left or right
- Gurantees Search Space is at least 2 in size at each step
- Post-processing required. Loop/Recursion ends when you have 1 element left. Need to assess if the remaining element meets the condition.
Template #3 (left + 1 < right):
- An alternative way to implement Binary Search
- Search Condition needs to access element's immediate left and right neighbors
- Use element's neighbors to determine if condition is met and decide whether to go left or right
- Gurantees Search Space is at least 3 in size at each step
- Post-processing required. Loop/Recursion ends when you have 2 elements left. Need to assess if the remaining elements meet the condition.
Other types of Binary Search for Practice:
Applying Binary Search to BST -- In this problem, we apply Binary Search concepts to a BST: LC #270: Closest Binary Search Tree Value
Binary Search With 2 Arrays -- In this problem, we need to compare values from 2 arrays to determine our search space: LC #4: Median of Two Sorted Arrays
Check out the animation below for an interactive experience on a different dataset:
Time and Space Complexity
Runtime: O(log n) -- Logorithmic Time
Because Binary Search operates by applying a condition to the value in the middle of our search space and thus cutting the search space in half, in the worse case, we will have to make O(log n) comparisons, where n is the number of elements in our collection.
- Binary search is performed by dividing the existing array in half.
- So every time you a call the subroutine ( or complete one iteration ) the size reduced to half of the existing part.
- First N become N/2, then it become N/4 and go on till it find the element or size become 1.
- The maximum no of iterations is log N (base 2).
Space: O(1) -- Constant Space
Although, Binary Search does require keeping track of 3 indicies, the iterative solution does not typically require any other additional space and can be applied directly on the collection itself, therefore warrants O(1) or constant space.
Binary Search is an immensely useful technique used to tackle different algorithmic problems. Practice identifying Binary Search Problems and applying different templates to different search conditions. Improve your approach to tackling problems, notice the patterns and repeat!