In computer science, you have many technique options when it comes to searching for an item. And you can either locate an item using linear search or binary search. These two are among the most common search methods. In today’s post, AlgoMonster will analyze these two popular search algorithms.
What is binary search about?
A sorted list contains information about the location of the target. Even comparisons that don’t pinpoint the target won’t reveal this information. They also reveal the target’s position in relation to the other items on the list. You can use this information to refine your search.
How does the searching process perform?
Binary search uses the strategy of checking the middle item in the lists. If the target does not match the target, the search continues.
When the target is smaller than the middle item, then the target must appear in the first half which contains elements lower than the middle one.
However, when the target’s value is greater than that of the middle item, then it indicates that the target must be somewhere in the higher part of the list.
Also, through each one comparison, it reduces by half the number of items you need to check the next step.
The search continues by looking for the middle of the list. If the target is not there, the search narrows down the search space to the other half of the list. The process of splitting will not stop until either the target is found or the remaining items don’t include the target.
Steps of using binary search algorithm (pseudocode)
- Location = -1;
- While ((more than one value in the list) and (haven’t found target yet)).
2A. check the middle value
2B. (( if the middle is the target) then, (have found target))
Otherwise,
2C. If (middle value is higher than the target)
Remaining list: the lower half
Otherwise, (middle value is lower than the target)
2D. remaining list: the higher half
End while
- If (you have located the target value)
The location of the target is the position of the target in your original list.
- Finally, return location as the result.
Analysis of the steps of binary search
This algorithm might make it appear that the list is being changed. However, it should remain the list the same as the original one. Therefore, it just changes the search space.
It might need the list again to search for other elements. Also, deleting half of a list and making copies of a list take extra effort, leading to the loss of efficiency.
Thus, the algorithm modifies the part of the list that is to be searched, rather than changing the entire list.
The search ends when it spots the target value. If the values of first and last cross over, then last is lower than first. This indicates that there are no remaining items on the list to verify.
Binary search: efficiency analysis
For binary search, you need to count the number and quality of comparisons in each case. If the middle value is your target, it’s the best case. One comparison!
What about the worst case? If the target does not appear in the list, the process of cutting it in half will continue until only one item remains.
Let’s check out the pattern for the number of comparisons following each division. Suppose an initial list length of 512 characters (an even power of 2) and an exact division of each iteration:
| Number of the remaining values to search | Number of comparisons till now |
| 512 | 0 |
| 256 | 1 |
| 128 | 2 |
| … | … |
| 1 | 9 |
From the table above, we can see there are 9 comparisons for a list size 512.
N is the list length and C is the number of the worst-case scenario comparisons. Then, C = log2N.
Therefore, we use a logarithmic function to describe the binary search efficiency:
| Case | Number of comparisons (when n=1024) | Number of comparisons (n) |
| Fewest comparisons | 1 | 1 |
| Most comparisons | 10 | Log 2 (n) |
What is linear search about?
What is the direct and simple way to search through a list of values? Start with the first element, then the second, and so forth until you find the target or come to the end of the list. This approach is what we call linear search.
How to compare the efficiency of algorithms?
An efficient algorithm would take less time, so one way to measure this would be to create programs for each algorithm to be compared and executed, as well as to measure the time it takes each to complete. The length of the list and whether the target is included in the list determine the number of steps. The comparison of the list value and the target value are the key steps for search algorithms.
Normally, the best-case analysis is not able to tell us much. If the target is the first element to be checked, then any algorithm will only make one comparison. Thus, let’s compare the worst and most common cases.
The efficiency of using linear search
It is obvious that as the list grows, the number required for locating a target item within both the worst and the average cases increases linearly.
So, a list with length N has the worst case being N comparisons while the average is N/2. Let’s see when n=1,000:
| Case | Comparisons when n=1,000 | The number of comparisons (in terms of n) |
| Best case with the fewest comparisons | When target is the first value: 1 | 1 |
| Best case with the most comparisons | When target is the last value:1,000 | n |
| Comparisons on average | When target is the middle value:1,000/2=500 | n/2 |
Linear search is a type of algorithm that uses linear functions to maximize efficiency. The number of comparisons needed to find a target increases linearly in proportion to the list’s size.
Conclusion: efficiency comparison between linear search and binary search
For a list of 100,000 values, the worst possible number of comparisons would be 16. However, linear search has to handle all 100,000 comparisons! When the list we need to deal with contains 200,000 values, the maximum number of comparisons for binary search would be 17. But it’s extremely huge for linear which is 200,000 times of comparisons!
So, binary is much faster in the worse case when it comes to large datasets.
