DEV Community

loading...
Cover image for Binary Search Algorithm Explained
TechLearners

Binary Search Algorithm Explained

skinan profile image Muhammad Sakib Khan Inan Updated on ・4 min read

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.

Thumbnail

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()
Enter fullscreen mode Exit fullscreen mode

✴️ 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);
    }
}
Enter fullscreen mode Exit fullscreen mode

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

Discussion (7)

pic
Editor guide
Collapse
eliseydev profile image
Elisey

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?

Collapse
skinan profile image
Muhammad Sakib Khan Inan Author

Thanks for the correction. I have corrected the mistake.

Collapse
dewhallez profile image
Akinwale

Great explanation.

Collapse
skinan profile image
Muhammad Sakib Khan Inan Author

Thanks for the appreciation!

Collapse
zawed123 profile image
Zawed Akhtar

Good Explanation

Collapse
skinan profile image
Muhammad Sakib Khan Inan Author

Thanks for the appreciation!

Collapse
abhiprojectz profile image