Introduction About Binary Search Algorithm
When you are writing programs for various applications, you will always need to perform search operations. If you want to perform file operations like retrievals or indexing, the functionality search plays a vital role. There are two search techniques available like the Binary search and Linear search.
In this blog, we will learn about a particular search technique called the Binary search algorithm. We will also learn about the time complexity of binary search and space complexity of binary search.
Binary Search Algorithm
Now let’s understand what an algorithm means. An algorithm is a collection of step-by-step instructions to resolve a problem. The binary search algorithm is a searching technique to find a particular element from a collection of data which is in a sorted form.
What binary search algorithm does is it searches the desired search element by comparing with the middle element of the data collection, which is in sorted form.
On performing the search, if the desired element is the same as the middle element, then the index of the middle element is returned. In this case, there is exact matching of the desired element with the middle element. So this search is considered highly successful. In another scenario, if the middle element is greater than the desired, the algorithm searches for the element in the array to left of the middle element. In another scenario, the desired element is searched for in the array to the right of the middle element. This search goes on until the size of the array is 0.
Functioning of the binary search algorithm
The first foremost key point to keep in mind is that a binary search algorithm always works on a sorted list. So you need to first sort the list provided. Then the desired element is checked with the middle element.
- If the desired element exactly matches with the middle element, then the index is returned as the output.
- If the desired element is greater than the middle element, then the right side of the array is not considered.
- If the desired element is smaller than the middle element, then the left side of the array is not considered.
- The search continues until the desired element is obtained from the list. If the desired element is matched, then the search is considered successful. If there is no match, then the search is considered unsuccessful.
Let us consider an example for better understanding of the binary search algorithm.
Consider the list as follows
2, 14, 22, 8, 7, 13, 9, 4, 26
Lets us consider the desired value to be 26. Here the total number of values in the list is 9.
Step 1: Sort the list
Example list : 2, 14, 22, 8, 7, 13, 9, 4, 26
Sorted list : 2, 4, 7, 8, 9, 13, 14, 22, 26
We see that there are 9 elements in the list, so the middle index is 5. The element at the index 5 is 9.
Step 2 : The desired element is compared with the middle element that is 9. Our desired element is 26. If the desired value is matched, then return the index as output and the search is terminated.
Step3 : Since 26 is greater than 8, the left side of the list is ignored and the right side of the list is traversed.
The new list to be searched is as follows
13, 14, 22, 26
Now consider 22 as the middle element and the search is continued.
The desired element 26 is compared with the middle element which is 22. If the desired value is matched, then the index is returned else the search continues.
Step 4: Since the desired value 26 is greater than 22, the middle element, the left side of the list is ignored and traversing happens on the right side of the list.
The new list is as follows:
26
We see there is only one element, then this is considered the middle element and the search begins. The desired element is 26 and the middle element is 26 as well. Thus the desired element and the middle element matches, then the index of the middle element is returned as the output. The binary search is considered as successful.
Time Complexity of Binary Search
The run-time complexity of the binary search algorithm is O(log n).
Best case time complexity of binary search algorithm
The best time complexity would be O(1) when there is an exact match of the search item with the middle item. This kind of binary search is considered highly successful. The desired element is matched and returned in the first step itself. Hence this is the best time complexity of binary search algorithm.
Worst case time complexity of binary search
If the search does not provide the desired element i.e. when there are no elements in the list similar to the desired element, then the binary search is unsuccessful. The worst case time complexity of binary search algorithm is O(log N).
Space Complexity of Binary Search
The space complexity of binary search algorithm is obtained based on the implementation of the algorithm.
There are two methods to implement the algorithm. They are
- Iterative method
- Recursive method
Recursive method: In this method there is no looping involved. The values are passed to the next recursion. The maximum and minimum boundary conditions are used in recursion.
Iterative method: In this method, there is looping involved. Here values are passed to the next iteration in the loop. The looping conditions play the role of controlling the iterations.
Summary
Best case time complexity is O(1)
Worse case time complexity is O(logN)
Space complexity of binary search is:
Recursive: O(logN)
Iterative: O(1)
Benefits
- A binary search algorithm is a straight-forward algorithm to implement.
- It is much faster than linear search.
- It is a very useful type of algorithm since the binary search algorithm eliminates half of the list on each and every search while making the comparison.
A quick stage-wise recap on binary search algorithm
- Stage 1 – Obtain the desired search element from the user
- Stage 2 – Locate the middle element in the list
- Stage 3 – Compare the middle element in the list with the desired search element
- Stage 4 – If the desired search element matches with the middle element, then display the output – “Desired Search Element Found” and exit
- Stage 5 – If the desired search element is not found with the first search, then the search process continues.
Conclusion
In this blog we have learned about binary search algorithm, how it is implemented, its functioning and benefits in detail. In programming, binary search algorithm plays an important role and is the most commonly used algorithm. It works very well on huge data collection. The biggest advantage of binary search algorithm is the best time and space complexity compared to other search algorithms. The only downside of the binary search algorithm is that the list/array should be in a sorted form. If there is only one search involved, then opting for linear search is a wise idea. If there are multiple searches involved, then binary search is the best bet.
Finally, we use binary search algorithm to search for a particular item from large chunks of data. Obviously the time consumption is more when dealing with large collection of data. That is when the binary search algorithms come to the rescue and make our work faster and more efficient.
