Binary Search Unveiled: A Beginner’s Guide to Efficient Data Searching :)

Introduction:

Searching is the most used feature in every domain. Previously I have written an article on Linear search as well so you can refer that below for understanding the simplest searching algorithm (linear search).

Linear Search Algorithm: Explained in easy and simple way :)

Binary search is one of the searching algorithms which is useful when we want to search in data which is sorted. In fact, it is mandatory to have list/ data in sorted order so that this algorithm works accurately and efficiently.

This algorithm follows divide and conquer approach where the list is divided into 2 parts and a middle element is found based on the length of list. Now obviously the array is in sorted order (as I said above), so in the LHS of the middle element that we found, there will be only nos less than middle element and on RHS there will be only nos greater than middle element. So depending on the comparison, we decide that whether we need to search for the element on LHS or RHS. So this directly halves the searhing process like we don’t need to traverse whole array as we did in linear search algorithm.

Working of Binary Search Algorithm:

Let’s say we have array/ list of 10 elements, then the indexing will be from 0 to 9. The start position would be 0 and end position would be 9 so we calculate middle element by using the below formula:

>> mid_position = (start_position + end_position) / 2

1. First of all, we set the loop condition as “while(start ≤ end)” which generally means until start position is less than or equal to end position, go on iterating and following the process of setting start and end position, calculating the mid element position and comparing with the element to be searched.
2. If we find that the mid position is equal to the element to be searched, then we directly return the mid element.
3. If the element to be searched is greater than mid element, that means we need to search for the element in the right hand side (RHS) part of the list/ array and now in this case, the end position will remain same but the start position will get changed to (mid position + 1) because we need to search in right part of the list.
4. If the element to be searched is lesser than mid element, that means we need to search for the element in the left hand side (LHS) part of the list/ array and now in this case, the start position will remain same but the end position will get changed to (mid position - 1) because we need to search in left part of the list.
5. In both the conditions we need to update the mid position right, so we need to update mid by using the formula mentioned above.
6. At last if the element is not found in the list, then return -1.

Code using Java:

package com.prashant.javaquestions;

public class BinarySearchDemo {
 
 /**
  * Takes an array and integer, returns index accordingly
  * @param arr The 1D array of integers
  * @param element The element to be searched
  * @return The index of element to find
  */
 public static int binarySearch(int[] arr, int element) {
  int start = 0;
  int end = arr.length - 1;
  int mid = (start + end) / 2;
  
  while(start <= end) {
   
   if(arr[mid] == element) {
    return mid;
   }
   
   // Go to right part when element is greater than mid
   if(element > arr[mid]) {
    start = mid + 1;
   }
   // Go to left part when element is lesser than mid
   else {
    end = mid - 1;
   }
   
   // Update mid
   mid = (start + end) / 2;
  }
  
  // Return -1 if element not found
  return -1;
 }

 public static void main(String[] args) {
  // Array in sorted order
  int[] arr = {17, 18, 19, 20, 26, 27};
  int element = 26;
  
  int result = binarySearch(arr, element);
  
  if(result != -1) {
   System.out.println("Element found at index: " + result);
  }
  else {
   System.out.println("Element not found...");
  }
 }

}

Output of Java Code — When element is found :)

In the above output you can see that we have element = 26 to find in the array, so it is present in our array at position 5, hence it is returning the index as 4 in the output.

Output of Java Code — When element is not found :(

In the above output you can see that now we have element = 100 to find in the array, so it is not present in our array right, hence it is returning the index as -1 (which represents that element does not exist). Further in main() method, I have just added a condition to display custom message when element is not found. It is optional.

Code using JavaScript:

Create an HTML file, paste this code into it and open the HTML file in the browser.

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">

    <style>
        /* Importing Google Fonts - Roboto */
        @import url('https://fonts.googleapis.com/css2?family=Roboto&display=swap');

        * {
            font-family: 'Roboto', sans-serif;
        }
    </style>

    <title>Binary Search using JavaScript</title>
</head>
<body>
    
    <script type="text/javascript">

        var arr = [11, 22, 33, 44, 55];
        var element = 33;

        function binarySearch(arr, element) {
            var start = 0;
            var end = arr.length - 1;
            var mid = Math.floor((start + end) / 2);

            while (start <= end) {
                if(arr[mid] == element) {
                    return mid;
                }

                if(element > arr[mid]) {
                    start = mid + 1;
                }
                else {
                    end = mid - 1;
                }

                mid = Math.floor((start + end) / 2);
            }

            return -1;
        }

        var result = binarySearch(arr, element);

        document.write("Array elements are: " + "&nbsp;");
        for(var i = 0; i < arr.length; i++) {
            document.write(" " + arr[i]);
        }
        document.write("<br>" + "Element to search: " + "&nbsp;" + element);
        
        if(result != -1) {
            document.write("<br>" + "Element found at index: " + "&nbsp;" + result);
        }
        else {
            document.write("<br>" + "Element not found...");
        }
    
    </script>

</body>
</html>

Output of JavaScript code on browser when element is found :)

Output of JavaScript code on browser when element is not found :(

Time Complexity:

1. Best Case: This case takes place when the element to be searched is present on the first index/ position in the array. i.e. when the first middle element itself is the element to be searched. hence the best case time complexity of binary search is O(1).
2. Worst Case: This case takes place when we have to keep reducing the search space till it has only one element (like when we keep on dividing the array until one element is left). hence the worst case time complexity of binary search is O(log N).
3. Average Case: In this case also, the time complexity will be O(log N). If you want to understand how it is calculated mathematically, you can view it by clicking here.

Space Complexity:

The space complexity of the binary search algorithm is O(1), which is constant space complexity.

Applications/ Real-life scenarios:

1. Databases and Data Retrieval Systems: In databases, especially those that store large amounts of sorted data, binary search algorithms are used for efficiently retrieving information. This is commonly seen in search engines, where binary search helps quickly locate relevant data based on search queries.
2. Library Catalogs and File Systems: Library catalog systems and file storage systems often use binary search algorithms to locate books, documents, or files based on specific criteria such as author, title, or filename. This ensures fast and efficient access to the required information.
3. E-commerce and Online Marketplaces: In e-commerce platforms, binary search algorithms are applied to search and locate products within specific categories or based on price ranges. This enables users to efficiently browse and find relevant products from the large set of inventories.
4. Mapping and Navigation Systems: Binary search algorithms are utilized in mapping and navigation applications to quickly search for locations, addresses, or points of interest within geographical datasets. This helps in providing fast and accurate directions to users.
5. Financial Systems and Stock Markets: In financial systems and stock markets, binary search algorithms play a crucial role in searching for specific financial records, stock prices, or trading information, which helps to fasten decision-making processes.

References:

• https://www.javatpoint.com/binary-search
• https://iq.opengenus.org/time-complexity-of-binary-search/

So that was all about binary search algorithm in simple and easy way.

That’s it for this article, hope you got to learn something🙂

Stay tuned for more articles like this one!!!