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 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 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 this,(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 ⭐
✴️ Code Implementation in Python
def main():
given_array = [1, 2, 3, 5, 8, 9, 11]
find = 8 # Number to search.
number_found = False # Determines if the number is found or not.
start_index = 0
end_index = len(given_array) - 1
while end_index > start_index:
mid_index = (end_index + start_index - 1) // 2
if given_array[mid_index] == find:
number_found = True
break
elif given_array[mid_index] > find:
end_index = mid_index - 1
else:
start_index = mid_index + 1
if number_found:
print("The Desired Element Is Present!")
else:
print("The Desired Element Is Not Present")
if __name__ == "__main__":
main()
✴️ Code Implementation in C++
#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
int arr[7]= {1, 4, 6, 8, 9, 10, 12}; // given array.
int y = 9; // Element to search is stored in variable y.
int l = 0; // l = Lower Index
int h = 7; // h = Higher Index
int m; // m = Middle Index
// Start of the loop to perform "Binary Search Algorithm".
while(l <= h) // The loop will run until there is one element left in array.
{
m = (l + h)/2; // Find the mid to divide the array into two almost equal parts.
if(y == arr[m]) // If the element is in the mid, we found it!
{
break; // Break the loop.
}
if(y < arr[m]) // If search element is lesser than element at the mid, cut the higher part of the array.
{
h = m - 1;
}
else // Else cut the lower part of the array.
{
l = m + 1;
}
}
if(l > h)
{
printf( "%d not found\n", y);
}
else
{
printf( "%d found!", y);
}
}
Conclusion
So far, I’ve tried to show everything steps by step, and below, the discussion section is open for your opinion to share and of course the questions if any. And don't forget to follow us.
💡 AND SUBSCRIBING to our YouTube TechLearnersInc and Telegram t.me/TechLearners will be amazing.
🌟 Thank you for reading. Keep coding, keep sharing! 🌟
📌 Featured in DEV Community's Twitter
The Binary Search Algorithm is the easiest illustration of how “Divide and Conquer” works.
{ author: @SakibInan } #DEVCommunity dev.to/techlearners/b…15:43 PM - 28 Dec 2020
Top comments (6)
There is a mistake in cpp example. It would not even compile. Array is set of 5 elements, but initializers are greater than 5. Also confusing mixing C and C++ style. For what reason include iostream and stdio.h?
Thanks for the correction. I have corrected the mistake.
Great explanation.
Thanks for the appreciation!
Good Explanation
Thanks for the appreciation!