What is Binary Search Algorithm?
In every computational system, developing search functionalities is a critical aspect. From retrieving files to indexing, search techniques are used in many applications. The binary search technique is one of the many search techniques commonly used for computation. It is one of the vital algorithms crucial for reducing computational complexities. The search algorithm is popularly used for effectively searching elements in sorted data structures.
The binary search algorithm systematically divides a search space into half on each iteration. It rapidly narrows down the possibilities, leading to prompt and reliable outcomes. This algorithm serves as an upgraded alternative to the much simpler linear search algorithm.
Table of Contents
Working Principle of the Binary Search Algorithm
The binary search algorithm is generally used to operate on a sorted array of lists. By following a divide-and-conquer approach, it efficiently locates a target element within a provided collection. The algorithm collates the target element with the middle element of the array and recursively narrows down the search range based on the comparison result.
The predominantly used first step in the binary search algorithm is sorting the list. When sorting is done, it’s time to search the median from the given list as per the value desired.
- If your desired value is worth the central index, then this value is returned as the answer.
- On the other hand, when the target value is seen to be smaller than the central index, then the right side of the list is ignored.
- The left half is rejected when the value desired is larger than the value of the central index.
- This process is continuously repeated on the shorted list till the formation of the target value takes place.
Example:
Situation 1:
To understand better, let us cite an example. Take a set of numbers:
3, 17, 25, 5, 6, 12, 19, 1, 29
Suppose our desired value is 29, and the list has a total of 9 elements.
Our initial step should be to sort this list. Post sorting, you will find this list to look as follows:
1, 3, 5, 6, 12, 17, 19, 25, 29
As this list has 9 elements in total, the central index will be at the 5th position. Here, you can find the central index to be 12. On the other hand, our desired value is 29, which is compared with the central index of 12.
It is clear that 12 is smaller than 29, so the left part of the list should be ignored. We can only navigate through the right side of the list. So the new list will be:
17,19, 25, 29
Note:
In regular practice, the list is not shortened. Narrowing the observations is what happens. Thus, the “new list” is not just shortening the existing list or creating a new list. Even though it can be used with a new list, two varied problems may arise.
- Firstly, memory overhead can take place. With every new list, the space complexity keeps increasing.
- Secondly, tracking of the original indexes is needed on every iteration.
When the new index is found, it is considered either the second or the third element. This depends on the way of implementation. The value 25 can be compared with the value desired that is, 29. This is so because this value is more than the central index. As the value 23 is larger than the central index, the left half of the list is discarded. Now the list to navigate through has one element, which is 29. As the list has only one element, it is now the central element. So, now the value desired is compared with 29. As the two values match, 29 is retired as the index value of the actual or original list.
Situation 2:
If we have 2 as the desired value in the same list we were discussing, then the central index 12 is first compared with 2. As we can see that 12, the central index is greater than the desired value 2, we have to focus only on the left side of the list.
The new list will have:
1, 3, 5, 6
If we consider the middle or central element as our second element, the desired value of 2 is now compared with 3. As we know 3 is greater than 2, we will again consider the left-hand side of the list. So the new list now has 1 as the only element. This value will again be compared with the other elements. In this context, it can be seen that the values don’t match. So, breaking out of the loop is the only option which is denoted by an error text written as “value not found”.
Time Complexity Analysis of the Binary Search Algorithm
The time complexity of an algorithm is the total time it takes to run as a function of the input size. Analysing the time complexity of an algorithm helps us understand how its performance scales with larger inputs. In the case of the binary search algorithm, its time complexity is determined by the number of iterations required to find the target element.
The binary search algorithm follows a divide-and-conquer approach. It repeatedly divides the search range in half until the target element is found or the search range becomes empty. This logarithmic behavior gives the binary search algorithm its efficient time complexity.
To understand the time complexity of binary search algorithms in detail, follow the segment below.
- The first step includes dividing the search range into half. So, the maximum number of iterations required to find the target element is equal to the number of times the search range can be divided into half.
- Suppose you have an array of size “n”. The maximum times it can be divided is log2(n). This is the case, as dividing the array at most log2(n) times will reduce the search range to a single element.
- Thus, O(log n) is the time complexity of the binary search algorithm, where n represents the size of the input array.
The efficiency of the logarithmic time complexity of the binary search algorithm is high. With the increase in size input, the number of iterations needed to search the target element grows very slowly.
For instance, if your array size is 1000, it can take a maximum of 10 iterations to find the target element. On the other hand, if you have an array size of 1,000,000, it can take a maximum of 20 iterations.
When you compare this with linear search, where the time complexity is O(n), and n denotes an array size, the binary search algorithm shows notable improvement in terms of time efficiency. In the worst-case scenario, a linear search may need to scan the entire array; on the contrary, a binary search eliminates half of the remaining elements in every step.
It is critical to understand that the binary search algorithm considers the input array as already sorted. If the array is not sorted, one extra step for sorting the array is necessary. This step increases the overall time and space complexity of the binary search.
Space Complexity Analysis of the Binary Search Algorithm
To understand what is the complexity of binary search algorithm, it is important to consider space complexity along with time complexity. Space complexity denotes the space or memory required by an algorithm to execute as a function of the input size. Assessing an algorithm’s scalability and memory requirements. In the case of the binary search algorithm, the space complexity is primarily determined by the recursive calls and any additional data structures used.
You can utilise binary search space complexity in multiple ways, which are a matter of discussion in this section.
Recursive Call Method
You can implement the binary search algorithm by using recursion. Every recursive call creates a new stack frame. These stack frames have variables, return addresses, and various other information. The number of recursive calls depends on the depth of the binary search tree. It is determined by the number of iterations required to find the target element. Hence, it can be said that the space complexity of the binary search algorithm using the recursive method is proportional to the depth of the binary search tree.
Iterative Method
One can iteratively implement a binary search algorithm using loops. In such cases, there are no recursive calls. Besides, the space complexity is constant, irrespective of the input size. Only a few variables are required to keep track of the lower and upper bounds and the middle index during each iteration. Therefore, the space complexity of the iterative implementation of the binary search algorithm is O(1).
Exceptional Case of Additional Data Structures
The binary search algorithm does not itself require any additional data structures excluding the input list or array. But if the algorithm includes added data structures like auxiliary arrays, queues, or trees, their space requirements should also be considered. For instance, if an additional list is used to store intermediate results or to help in the process of search, the space complexity would depend on the list size.
Advantages and Disadvantages of Binary Search
Advantages
The use of a binary search algorithm is vast due to its high efficiency in locating target elements in sorted lists. Here are the prime advantages of this algorithm that users can witness.
Easy to Implement
The binary search algorithm is relatively simpler and straightforward to implement. Both recursive and iterative methods work well depending on the programming languages and preferences. The simplicity of the algorithm and its well-defined steps make it accessible to programmers of different skill levels.
Makes Search Space Half
As binary search operates by continuously dividing search space in half, it eliminates a large portion of the remaining elements in every step. This property makes binary search highly efficient, especially for large datasets. By halving the search space in each iteration, binary search narrows down the possibilities quickly, making it an optimal choice for sorted arrays or lists.
Enhanced Time Complexity
Binary search algorithm has a time complexity of O(log n); here, n is the size of the input. This logarithmic time complexity makes binary search significantly faster than linear search, which has a time complexity of O(n). As the size of the input increases, binary search requires fewer iterations to find the target element, resulting in enhanced performance.
Wide Application
You can use binary search for many purposes, along with searching for specific elements from collections. From finding an element’s position to determining the presence of a value in a sorted list, binary search can be used in many ways. It is a fundamental building block in other advanced algorithms and techniques, including binary search trees.
Best Practices and Tips for Utilising Binary Search Effectively
The use case of the binary search algorithm is not limited to just sorting arrays of lists. Below are two distinct patterns that can help solve problems related to binary search in almost 90% of cases.
Separating Condition
In this approach, you can use a variation of binary search to find the first occurrence of a specific element in an array, given a clear property that separates the right and left halves of the list or array around the target answer.
For instance, consider an array that contains some elements of value 2, this is followed by a few elements 0, and there are also a few elements with value 1. Looks like- (2,2,0,0,0,1,1).
By observing the array, we notice that everything to the left of the first occurrence of 1 consists of elements that are either 2 or 0, while everything to the right is 1. This property serves as the separation criterion for your search.
During the binary search, the element at the middle index, arr[mid], is checked. If arr[mid] is equal to 2 or 0, we know that the desired value lies on the right side of the array because the separating condition is not satisfied. Therefore, we update the lower bound by setting ‘low’ to
mid + 1. Conversely, if arr[mid] is equal to 1, we have encountered the first occurrence of the desired value. However, to ensure that we find the actual first occurrence, we continue searching on the left side. Therefore, we update the upper bound by setting ‘high’ to mid-1.
Monotonic Relation
When there is a scenario where you observe a consistent relationship between two variables and aim to determine the minimum or maximum value of one variable while adhering to a constraint on the second variable, a binary search approach can be employed.
For instance, if you want to find the smallest number whose cube exceeds 999, you can use binary search as follows:
Here, you have two variables, x and y= x³, which showcases a monotonic relationship (i.e., an increase in x leads to an increase in y). Rather than employing a linear search by calculating and comparing cubes (1³, 2³, 3³, and so forth), we can leverage binary search within a certain range. By examining the midpoint value, we calculate its cube. If it exceeds 999, you need to adjust your search to lower values (updating the upper bound). On the other hand, if the cube is less than 999, you should search for larger values (updating the lower bound).
Comparison with Other Search Algorithms
Binary Search Vs Linear Search
Linear search and binary search are two common algorithms used to find an element in a list. The linear search checks each element sequentially until the target is found or the end of the list is reached. It is simple but inefficient for large lists. On the other hand, binary search is a more efficient algorithm that works on sorted lists. It repeatedly divides the search space in half, comparing the target with the middle element and discarding the irrelevant half.
Binary Search Vs Hashting
Binary search and hashing are two different techniques used for searching in data structures. The binary search is efficient for sorted arrays and offers logarithmic time complexity, while hashing provides constant-time complexity for retrieval but requires additional memory for hash tables and hashing functions.
Conclusion
The binary search algorithm is a potent tool that offers numerous benefits in terms of efficiency. By leveraging the inherent properties of sorted data, binary search allows for a significant reduction in the number of comparisons required to find a target element. This advantage makes it a preferred choice for searching large datasets, particularly in computer science and information retrieval applications.
Trending Blogs
