Binary Search in Data Structures

Binary Search in Data Structures

06 Jun 2024
Intermediate
12.3K Views
25 min read
Learn via Video Course & by Doing Hands-on Labs

Free DSA Course with Certificate (Online)

Binary Search: An Overview

In the previous tutorial, we saw that linear search is inefficient for large and sorted arrays as it ends up searching the entire array to find an element. It becomes time-consuming. To overcome this limitation of the linear search algorithm, we have the binary search technique with us.

In this DSA tutorial, we are going to look in detail at the Binary Search. We will learn its features, working, implementation, etc. To further enhance your understanding and application of binary search concepts, consider enrolling in the best Data Structures And Algorithms Certification to gain comprehensive insights into effective data structure utilization for improved problem-solving and time management.

What is Binary Search in Data Structures?

It is a searching algorithm that searches for an element's position in a sorted array only. If the elements are not sorted already, we need to sort them first to apply the binary search technique. Sorted here means that the elements will either be in a natural increasing or decreasing order.

This search technique involves dividing a large dataset into smaller subsets until the desired item is found. It repeatedly divides in half the portion of the list and tries to find the element in one or the other half until the element is found or the array is exhausted. Thus, the element is always searched in the middle portion of an array

Binary Search Algorithm

Step: 1 Start by defining the search interval/space: the entire array or list in the beginning.
Step: 2 Divide the search space into two halves by finding the midpoint. 
Step: 3 Compare the middle element of the search space with the key. 
Step: 4 If the key matches with the middle element, the search is complete and the index of the value is returned. The process is terminated.
Step: 5 If the key does not match with the middle element, choose which half will be used as the next search space.
           If the key is smaller than the middle element, the left half is used for the next search.
           If the key is larger than the middle element, the right side is used for the next search.
Step: 6 Again start with step 2.
Step: 7 This process is continued until the key is found or the total search space is exhausted.    

Working of Binary Search Algorithm in Data Structures

Initial Array in Binary search

Let's suppose we need to find the element 17 i.e. key=17 in the given array or list. We will work according to the above-given algorithm.
  1. Set two pointers low and high at the lowest and the highest positions respectively.

    Setting Pointers in binary search

  2. Find the middle element mid of the array ie. arr[(low + high)/2] = arr[(0+6)]/2] = arr[3] = 44

    Mid element in binary search

  3. If the element key == mid, return the index of mid. Otherwise, compare the element to be searched with mid.
    • If key > mid, compare the key with the middle element of the elements on the right side of mid. This is done by setting low to low = mid+1.
    • Otherwise, compare the key with the middle element of the elements on the left side of mid. This is done by setting high to high = mid-1.

    Finding mid element

  4. Repeat steps 2 to 3 until low meets high.

    Mid element

  5. key = 17 is found.

    key is found

Read More - DSA Interview Questions and Answers

Implementation of Binary Search Algorithm in Different Programming Languages

There are mainly two ways to implement the Binary Search Algorithm in Data Structures, using recursion and iteration. Let us look at each of them.

  1. Recursive Binary Search

It follows the divide and conquer approach.

Recursive Binary Search Algorithm

binarySearch(arr, key, low, high)
    if low > high
        return False 
    else
        mid = (low + high) / 2 
        if key == arr[mid]
            return mid
        else if key > arr[mid]        // key is on the right side
            return binarySearch(arr, key, mid + 1, high)
        else                               // key is on the left side
            return binarySearch(arr, key, low, mid - 1)    

Example of Recursive Binary Search Algorithm in Different Languages


def binarySearch(array, key, low, high):
    if high >= low:
        mid = low + (high - low) // 2

        # If found at mid, then return it
        if array[mid] == key:
            return mid

        # Search the left half
        if array[mid] > key:
            return binarySearch(array, key, low, mid - 1)

        # Search the right half
        return binarySearch(array, key, mid + 1, high)

    return -1

array = [4, 17, 32, 44, 75, 80, 86]
print("The array to be searched is: ", array)

key = 80
n = len(array)
result = binarySearch(array, key, 0, n - 1)

if result == -1:
    print("Not found")
else:
    print("Element is found at index", result)
    

import java.util.Arrays;

public class BinarySearch {
    static int binarySearch(int[] array, int key, int low, int high) {
        if (high >= low) {
            int mid = low + (high - low) / 2;

            // If found at mid, then return it
            if (array[mid] == key) {
                return mid;
            }

            // Search the left half
            if (array[mid] > key) {
                return binarySearch(array, key, low, mid - 1);
            }

            // Search the right half
            return binarySearch(array, key, mid + 1, high);
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] array = {4, 17, 32, 44, 75, 80, 86};
        
        System.out.print("The array to be searched is: ");
        System.out.println(Arrays.toString(array));

        int key = 80;
        int n = array.length;
        int result = binarySearch(array, key, 0, n - 1);

        if (result == -1) {
            System.out.println("Not found");
        } else {
            System.out.println("Element is found at index " + result);
        }
    }
}
    


#include <iostream>
using namespace std;

int binarySearch(int array[], int key, int low, int high) {
  if (high >= low) {
    int mid = low + (high - low) / 2;

    // If found at mid, then return it
    if (array[mid] == key)
      return mid;

    // Search the left half
    if (array[mid] > key)
      return binarySearch(array, key, low, mid - 1);

    // Search the right half
    return binarySearch(array, key, mid + 1, high);
  }

  return -1;
}

int main(void) {
  int array[] = {4, 17, 32, 44, 75, 80, 86};
  cout << "The array to be searched is: ";
    for (int i : array) {
      cout << i << ", ";
    }
  cout << std::endl;
  int key = 80;
  int n = sizeof(array) / sizeof(array[0]);
  int result = binarySearch(array, key, 0, n - 1);
  if (result == -1)
    printf("Not found");
  else
    printf("Element is found at index %d", result);
    

Output

The array to be searched is: 4, 17, 32, 44, 75, 80, 86, 
Element is found at index 5 

  1. Iterative Binary Search

    This iterative implementation of the binary search algorithm involves a loop to keep dividing the search space in half until the target value is found or the search space is empty.

    Iterative Binary Search Algorithm

    do until the pointers low and high meet each other.
        mid = (low + high)/2
        if (x == arr[mid])
            return mid
        else if (x > arr[mid]) // x is on the right side
            low = mid + 1
        else                       // x is on the left side
            high = mid - 1 

    Example of Iterative Binary Search Algorithm in Different Languages

    
    def binarySearch(array, key, low, high):
        while low <= high:
            mid = low + (high - low) // 2
    
            if array[mid] == key:
                return mid
    
            if array[mid] < key:
                low = mid + 1
            else:
                high = mid - 1
    
        return -1
    
    array = [4, 17, 32, 44, 75, 80, 86]
    print("The array to be searched is:", end=" ")
    print(*array, sep=", ")
    key = 32
    result = binarySearch(array, key, 0, len(array) - 1)
    if result == -1:
        print("Not found")
    else:
        print(f"Element {key} is found at index {result}")
        
    
    public class BinarySearch {
        static int binarySearch(int[] array, int key, int low, int high) {
            while (low <= high) {
                int mid = low + (high - low) / 2;
    
                if (array[mid] == key)
                    return mid;
    
                if (array[mid] < key)
                    low = mid + 1;
                else
                    high = mid - 1;
            }
    
            return -1;
        }
    
        public static void main(String[] args) {
            int[] array = {4, 17, 32, 44, 75, 80, 86};
            System.out.print("The array to be searched is: ");
            for (int i : array) {
                System.out.print(i + ", ");
            }
            System.out.println();
            int key = 32;
            int result = binarySearch(array, key, 0, array.length - 1);
            if (result == -1)
                System.out.println("Not found");
            else
                System.out.println("Element " + key + " is found at index " + result);
        }
    }
        
    
    #include <iostream>
    using namespace std;
    
    int binarySearch(int array[], int key, int low, int high) {
        while (low <= high) {
            int mid = low + (high - low) / 2;
    
            if (array[mid] == key)
                return mid;
    
            if (array[mid] < key)
                low = mid + 1;
            else
                high = mid - 1;
        }
    
        return -1;
    }
    
    int main(void) {
        int array[] = {4, 17, 32, 44, 75, 80, 86};
        cout << "The array to be searched is: ";
        for (int i : array) {
            cout << i << ", ";
        }
        cout << endl;
        int key = 32;
        int n = sizeof(array) / sizeof(array[0]);
        int result = binarySearch(array, key, 0, n - 1);
        if (result == -1)
            printf("Not found");
        else
            printf("Element %d is found at index %d", key, result);
    
        return 0;
    }
        

    Output

    The array to be searched is: 4, 17, 32, 44, 75, 80, 86, 
    Element 32 is found at index 2   

    Binary Search Complexity Analysis

    1. Time Complexity
      CaseTime Complexity
      Best Case

      O(1)

      Average Case

      O(log n)

      Worst Case

      O(log n)

    2. Space Complexity: As we are not using any significant extra memory in Binary Search, the space complexity is constant, i.e. O(1).

    Applications of Binary Search

    1. In libraries of Java, .Net, C++ STL.
    2. The binary search is used to pinpoint the place where the error happens while debugging.
    3. It can serve as a building block for complicated machine learning algorithms, such as those for training neural networks.
    4. It can be used to search in computer graphics algorithms like ray tracing or texture mapping.
    5. It can be applied to database searches.

    Advantages of Binary Search

    1. It is faster than linear search, especially for large arrays since its run time complexity is O(logN).
    2. More efficient than other searching algorithms with a similar time complexity, such as interpolation search or exponential search.
    3. At each iteration, the binary search algorithm eliminates half of the list and significantly reduces the search space.
    4. Binary search is well-suited for searching large datasets that are stored in external memory, such as on a hard drive or in the cloud.
    5. It even works on a rotated array.

    Disadvantages of Binary Search

    1. Binary search requires that the array be sorted before the algorithm is applied. If the array is not sorted, then the algorithm cannot be used.
    2. Binary search requires that the data structure being searched be stored in contiguous memory locations.
    3. If the array is being updated dynamically, i.e., new elements are added or old elements are deleted, then the binary search cannot be used as it requires the array to be static.
    4. It requires that the elements of the array be comparable, meaning that they must be able to be ordered.
    5. The recursive binary search method uses stack space.
    Summary
    So, here we saw every aspect of the binary search algorithm in data structures. It must not have been that difficult to understand as compared to linked lists or doubly linked lists. Just make sure you are thorough with arrays in data structures. To apply your knowledge of linear search algorithms, enroll in our Best Dsa Course.
    Share Article

    Live Classes Schedule

    Our learn-by-building-project method enables you to build practical/coding experience that sticks. 95% of our learners say they have confidence and remember more when they learn by building real world projects.
    Generative AI For Software Developers Jul 20 SAT, SUN
    Filling Fast
    08:30PM to 10:30PM (IST)
    Get Details
    Angular Certification Course Jul 20 SAT, SUN
    Filling Fast
    06:00PM to 08:00PM (IST)
    Get Details
    Azure Master Class Jul 20 SAT, SUN
    Filling Fast
    03:00PM to 05:00PM (IST)
    Get Details
    ASP.NET Core Certification Training Jul 28 SAT, SUN
    Filling Fast
    07:00AM to 09:00AM (IST)
    Get Details
    Software Architecture and Design Training Jul 28 SAT, SUN
    Filling Fast
    05:30PM to 07:30PM (IST)
    Get Details
    .NET Solution Architect Certification Training Jul 28 SAT, SUN
    Filling Fast
    05:30PM to 07:30PM (IST)
    Get Details
    Azure Developer Certification Training Jul 28 SAT, SUN
    Filling Fast
    10:00AM to 12:00PM (IST)
    Get Details
    Advanced Full-Stack .NET Developer Certification Training Jul 28 SAT, SUN
    Filling Fast
    07:00AM to 09:00AM (IST)
    Get Details
    Data Structures and Algorithms Training with C# Jul 28 SAT, SUN
    Filling Fast
    08:30PM to 10:30PM (IST)
    Get Details
    Angular Certification Course Aug 11 SAT, SUN
    Filling Fast
    09:30AM to 11:30AM (IST)
    Get Details
    ASP.NET Core Project Aug 24 SAT, SUN
    Filling Fast
    07:00AM to 09:00AM (IST)
    Get Details

    Can't find convenient schedule? Let us know

    About Author
    Amit Kumar Ghosh (SDE and Mentor at Scholarhat)

    As a software developer with a wealth of experience, he brings a unique combination of technical acumen and a passion for mentorship to my role. With 6 years of experience, he has honed the skills in C/C++, Java, Python, SQL, C#, JavaScript, React, Java Spring etc. and has a proven track record of delivering high-quality, scalable software solutions and core Computer fundamental knowledge DSA, OOPs, CN, OS etc.

    As a teacher, his approach revolves around interactive techniques, prioritizing hands-on learning and real-world projects. He explains concepts clearly, offer practical examples, and encourage questions to foster a supportive environment.
    Accept cookies & close this