New to search algorithms? Do you feel confused sometimes when it comes to binary search? Is it always better than linear search? Well, for new learners of algorithms, you may encounter many questions like these. AlgoMonster is here to explain some basic concepts of binary search to help you.
Let’s play a game about guessing a number
Before we dive into any technical terms, let’s look at a simple example. In fact, you can play along with me here.
Say, I write down a number from 1 to 100 for you to guess. After hearing your number, if it’s not what I wrote down, I will tell you to go higher or go lower. So, all you need to do is to get the target number as soon as possible.
What do you think of this game? You have probably played many times before in fact. However, did you ever notice how you did it? Or do you know what’s the possibly best strategy to use as few guesses as possible?
We will tell you the answer after explaining the basics of binary search. Make sure you finish reading this post. Check it at the end of the article then.
What is binary search?
As a common search method, binary search is the fundamental algorithm in the computer data structure. Usually, people use binary search to locate a specific element in an array. And before you can use it, you need to arrange the elements in the array in sequential order. In other words, it is not possible to use this search technique in anunsorted array. To spot the target element, binary search first compares it with the middle element.
How does binary search work?
Binary search is used for finding the element within an array. To find the element, you can use the following concept: Binary search uses the middle value in the array to find the element. If the value is the same, it will return the output. If the two elements are not the same, it will identify if the middle value exceeds the element or not. Usually, it works in the following steps:
Locate the element in the middle.
Then, it will compare the middle one with the one you want to find.
It produces the output when these two elements are the same. Otherwise, it continues searching as follows.
If the values of the two elements are different, it will determine if the middle element value exceeds the element you’re looking for.
When the value of the element is higher than the middle element, the search will begin with the elements closest to the middle element.
If the value of the element is higher than the element in question, the search will begin with elements preceding the middle element.
The process won’t stop until it locates the target element.
An example of how it works
To understand this concept, we will use the following example. The following array has 9 elements. Suppose the element you want to find in the array is 8.
A [9] = 1, 3, 6, 8, 10, 13, 14, 16 and 20
First: The 1st element value in the array is 1. And the last element equals 20. in this array, the index begins at 1 and ends at 9. The median value in this list is in index 5.
Second: The value of the middle element 10 is higher than the target value which is 8. The algorithm will search the array first before it finds the middle element. So, it knows the possible location can’t be in the right half of the array. It will search the array from index value 1 through index value 4.
So, what’s the next step?
Third: Again, find the middle index value from the remaining half from step 2. Select the median value which is the second or third one.
Then you are likely to get 3 or 6. Well, if you choose the third index value, then you’ll get 6.
Fourth: Obvious, 6 is lower than your desire value 8. Thus, the search will continue with the element following the index value.
Fifth: The index value 5 already exceeds the element. Now, with the fourth step, we can identify that the element in index value 3 is less than the element. The remaining element is at the index value 4.
Sixth: Next, it will compare the element at index 4 with the target. Then, it finds the element you’re searching for. Hence, the algorithm will return 8 as its output.
What’s the idea behind the example?
Well, from the above explanation, it’s easy to see that we use the median value to identify the elements. Then, the algorithm used to create the median value will determine how the search is conducted.
Binary search has its limitations
When you have a sorted array, either in ascending or descending order, you can use the binary search algorithm to improve your efficiency. In other words, it doesn’t go with unsorted arrays.
Another drawback is that it is not always efficient. This is particularly true when the target value is not in the array. So, if the element you want to locate is not there, it will be time-consuming before you get the output. Thus, this will a waste of memory allocation and time.
Let’s go back to answer the guessing game at the beginning
So, from what we’ve discussed above. You may have probably known that the best possible strategy could be using binary search.
Well, by diving all possible guesses into two halves and picking the middle one, it cuts off half trails, right? Thus, it could be the best possible guess.
Thus, you can start with 50. If I say go higher, you can eliminate the lower half which is from 1 to 50. So you may try 75, and then you dump one half if I say lower or higher. Continue this till you have what I’ve written.
For a small database, it seems not efficient. Say, my number is 1, it’s better to deal with it using linear search?
Conclusion
Binary search is an efficient search method. It normally locates a target value in a large database quickly. However, it has its limitations. Hopefully, these examples help you understand his algorithm better.
