When we want to find a specific element from an array, the most basic algorithm is linear search. For random elements in small datasets, it could be one of the efficient ways. However, when it comes to large datasets, it’s not suitable because it will be too time-consuming. Then, you will need another search algorithm that is relatively efficient: the binary search algorithm.
What is it? How does it perform? Don’t worry. AlgoMonster will explain binary search in this post to help you understand it better. Read on to find answers to these questions about search algorithms.
How does this search algorithm work?
This method divides an array into halves. Depending on the comparison between the middle value and the target value, each half is then discarded. Also, your search continues to the upper half of the lower half is based on the middle element. Then, we can repeat this process until the array size reaches one or two elements. After each search, we get the index of the element, or -1 if the element is not present.
Steps of how it works:
Binary search is a comparison of the element to be searched and the element in the middle.
1: Locate the element in the middle position. (mid = left + (right – left) / 2)
2: Verify the value of the middle component. Three possible scenarios are:
- The element you are looking for is the same as the middle element in the list. In this case, you’ve located what you are searching for, and you stop searching.
- The search element is higher than the middle element in the list. Then, the search space will be from the middle value to the last value in the list. In other words, you could just ignore the other half.
- The search element is smaller than the element in the middlemost. Therefore, the algorithm will continue the process of searching in the lower half. In other words, it keeps looking for the target from the first value to the value right before the middle one.
3: Continue repeating these two steps until you find the location of the element that you want. However, sometimes the target value is not present in the array. So, the last one is not what you are looking for, either.
The dry run of using binary search to locate a number in the sorted array
Here’s the sorted list of numbers:
| 9 | 13 | 18 | 25 | 27 | 30 | 32 | 33 | 35 | 55 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
As we know, this method only works with sorted arrays. And our target is 30.
So, left = 0, right = 9.
Then, mid = 0 + (9 – 0) / 2 = 4.5 = 4 (as we need integer value for index)
Note: key = 30.
Check the middle element
The middle position is in index 4 and the middle value is 27. Obviously, 27<30.
Therefore, keep looking for it in the upper half.
| 30 | 32 | 33 | 35 | 55 |
| 5 | 6 | 7 | 8 | 9 |
Now, let’s see how to decide the middle value:
Here, left = mid + 1 = 5, and right = 9, then, mid = 5 + (9 – 5) / 2 = 7.
The middle position is index 7 with the middle element of 33. Again, it’s not what we want. And this time, 33>30.
Locate the new middle
Now, left = 5, and right = mid – 1 = 6, making mid = 5 + (6 – 5) / 2 = 5.
| 30 |
| 5 |
Therefore, we successfully locate the target number which lies in index 5.
Two examples of binary search algorithm applications
Here are two examples of binary search applications.
Using it to debug a program
Using binary search to find bugs in a program is a popular way to debug programs. For example, two programs should perform the same algorithm, but one is faster than the other. The faster program may be buggy, producing incorrect results on a known test case. The correct program may have introduced bugs as it sped up.
You naturally use it in a guessing game
For instance, players are given an array of numbers ranging from one to one thousand. Suppose the written-down number is 700. So, the person guessing for this particular number picks the mid-value of the array-500. As someone will tell him it’s lower than the target. Thus, he will drop the elements below the mid-value of 500 and move to the upper side of the list. In other words, the process of searching continues with the higher half. The search cycle repeats until the item to be searched is found.
Binary search vs. linear search: what’s the difference?
In contrast to a linear search, a binary search algorithm is a recursive search. It identifies an element from a list by comparing it to the middle element in the list. By analyzing the middle element, the algorithm determines whether the target value is smaller or larger than the median.
On the other hand, linear search searches for the item from the very beginning of the data. Then, it will go through the elements one by one without skipping any, till then it locates the target value.
Binary search or linear search: O (n) vs. O (log n)
Let’s compare the worst-case scenarios.
If you want to find a name from an alphabetically sorted dataset. Or say to locate an item from 1 million elements that are arranged in ascending order.
On the other hand, you use linear search, say you have to go through all the elements like one thousand or one million times.
But with binary search, the most steps you need to locate it will be 20. Isn’t that astonishing?
Conclusion
A binary search algorithm is a very fast search algorithm that uses the divide and conquer principle. Also, it’s faster than linear in many cases.
Basically, it divides the list into two halves at each searching step. After comparing the target value with the middle value each time, the search will continue to the higher half or lower half accordingly. Until it locates the target or else, it will end the searching when there is only one left. Sometimes, the target is not present in the list.