In the world of computer science, Binary Search Algorithm is the ground of the “ Divide & Conquer ” algorithmic paradigm. This algorithm is the easiest illustration of how “Divide and Conquer” works. Using this algorithm searching can be done in O(log(n)) time where linear search takes O(n) time in the worst case. It saves time and makes the number of comparisons to perform fewer.
Let us consider a scenario. Suppose, you have a book of 1000 pages and we need to go to page number 580 and check whether the page exists or not. By using the linear search algorithm, you can start looking for the desired page from the beginning or the end. In both ways, you have to search over a large number of pages to find the page number 580 as we are checking every page on our way. But, can we do it better? Can we find our desired page by making fewer comparisons? The answer is: Yes, we can do it in a faster way. We can do the improvement in less time by using the “Binary Search Algorithm”. First, we need to keep in mind that this algorithm can be correctly applied if the data is sorted. In the case of page numbers of a book, the data is sorted. Here, we have page numbers from 1 to 1000 in a sorted manner. We need to find the page number 580. Let’s divide our searching area into two halves. Get the midpoint of range 1 to 1000 like this, mid-index = (ending index+starting index-1)/2. So, it goes like these,(1000 / 2) = 500. Compare 500 (mid-index) with 580 (searching index). 580 is larger than 500 so it cannot be present in the range (1- 500). So, let’s exclude it from our searching area. Now, we have (501–1000) numbered pages for searching. Repeat the previous process and get the midpoint of the range (501 -1000). It will be 750. Compare 580 again with 750. And fix the new searching area as (501 -750) and exclude the range in which the number cannot be present. Keep repeating the process until you find the exact number or reach a situation when there are no numbers left to search. In this process, you can find the desired number in log(n) time and you need to perform a very fewer number of comparisons than linear search as after every comparison we are making our searching area small by excluding areas in which searching is unnecessary. So, the method is very simple when you have a sorted data set and need to find something in the data set rather than keep checking every element in the data set one by one, keep dividing the data set into two halves and compare the value with mid-value.
This algorithm is frequently used in small to big tasks in computer science. Some other important algorithms like Merge Sort also use the concept of divide and conquer. If you understand this algorithm well, you will get the basic idea of the “Divide & Conquer” paradigm which is surely going to help you in learning more complex algorithms in the future. The most important thing to remember is, whenever you are going to apply the binary search algorithm the data must be placed in a sorted manner otherwise you cannot apply binary search. If you are going to start competitive programming must know the binary search algorithm as you will find problems that needed to be solved by directly using the binary search algorithm or using the concept of the binary search algorithm.
I have attached here my code implementation of the binary search algorithm in Python & C ++ programming language.
Thank you for reading. Keep coding, keep sharing!If you like it, share it with others !