In today’s article about algorithms, algo.monster will introduce this common search technique – binary search. It will take you about 4 minutes to finish reading this post. Enjoy the tour to this search algorithm.
So, what is it about?
Binary search is a computer science method that allows you to find an item in a sorted set. This algorithm is faster than linear search. It will look through all items in the list to find a specific item. However, it has limitations. Before using a binary search algorithm, you need to arrange the list in order. Well, it can be ascending or descending.
Binary search works by repeatedly dividing the sorted list in two, and then working on the portion of the list that might contain the item you are searching for until the final list contains just one item.
What’s binary search?
The binary search algorithm can be used to locate the position of a particular value within a sorted array. This search algorithm uses the principle of divide and conquer. However, it is very fast and requires that the data be in a sorted format. The search begins in the middle of an array and then moves down to the lower or upper halves of the sequence. If the median value is lower than the target value, the search should go higher. If not, it will need to focus on the descending part of the array.
In computer science, people can call it a logarithmic or half-interval search as well.
The Explanation of Binary Search Algorithm
Binary search is a time-saving way to find a target value among a list of ordered elements. It can cut down on search space by starting in the middle of the end of the sorted list. Also, the median value is about to divide the list into two halves, either ascending or descending.
Example: with a target value 8 and a search area 1 to 11:
The median/middle element of the number list is determined and the pointer there is set. In this instance, it is 6.
So, during the searching process, you compare the target number 8 with each element that lies in the middle. The target of 8 >6. That means 8 must be in the higher half, which is the list from 7 to 11.
The target is compared with the pointer and the value of the pointer is moved to the next one(7). Because it is smaller, the pointer moves to a higher element.
Then 8 is a perfect match for the target.
This is the idea behind this method
Binary search only required the target to be compared with three values. It would have been much easier to do a linear search. Instead of starting with the first value, the binary search would have moved up and required the target to be compared to eight. Binary searches can only be done with ordered data. If the data are randomly arranged, a linear search will yield all of the results while a binary search will likely remain in an endless loop.
Example of how binary search method works
Imagine that you had 10,000 pages in a textbook and you accidentally burnt most of the pages away. Now you have a book that has approximately 300 pages. Those burnt pages are gone completely.
Normally, if you want to read some content from a certain page, say on page 500, you would open it at the center. But as we’ve mentioned, you only had 300 pages left. So, there’s the possibility that page 500 is not available in this book anymore, right?
Well, we don’t know. It is not clear if page 500 is the original page. There are pages 1-499, 501, and 600. It is not clear if this page is the final or any other. It is only known that, if it does exist, its pages will exceed 500 and those to the left of it will be less than 500.
Which strategy is best to find the page?
You can start with the first page, say it’s page 100. Next, you can go to 105, 108.110, and then on to 255. Then, you can move on to 256 and so on. Obviously, this is not a good approach.
Try this way now:
Now, open the book from the middle page. As we’ve mentioned, there are 300 pages in this book. Thus, if the page number you open is less than 500, you know that your page will appear in the second half of the book. Or else, it must be on the left side, which is the lower side.
Either way, you can locate it from the remaining 150 pages. Well, if it’s not burnt. Now, it is clear which half of your book does not contain page 500. Let’s say if your first try is page 606, so, apparently, 500<606. Then, 500 can’t be in the right half which is above 606.
For the remaining 150 pages, you will need to repeat this process.
Try the middle page and eliminate half of the pages. So here is how many pages you need to go through: 75, 37 or 38, 18 then 9, 5, and 3, then finally 2 left.
The conclusion from the example of finding the page
So, the first method we mentioned above is actually linear search. And the second one is what we’re talking about today: binary search.
Say if page 500 is somewhere in the middle, using linear search is definitely time-consuming. However, if this page is not existing, it’s hard to tell which is better. In the best case, say it is on the first page, linear is more efficient.
Now, how about using the binary search tree?
As the name tells, a binary search tree is just like the form of a tree. In this tree, you divide the main trunk into two halves. Each of these branches then becomes two and each one into two, and so forth. However, it is not infinite so assume that the branching process will end somewhere.
Grab your book and place it at the main trunk’s branching point.
The pages with numbers below this page will be shown on the left, while pages with higher numbers will be shown on the right. Continue the same process until you search all pages.
Conclusion
Binary search works perfectly with sorted elements in large datasets. It improves efficiency and saves much trouble.
