Binary Search in Data Structure

Suppose you want to search for a word starting with ‘U’ in a dictionary. A dictionary has thousands of words arranged in ascending order. If you start from the beginning and keep on searching you are going to exhaust soon with probably more than 90% of the dictionary still not looked through.

The better option is to go to the middle of the dictionary and look for the starting letter of that page. If the starting letter in the middle of the dictionary is lower than ‘U’ then you need to search only the second half of the Dictionary and if it is higher than ‘U’, you have to look in the first half of the Dictionary.

Repeat the same process for the selected half and now you have only a quarter of the dictionary to search from. Continue this process multiple times. In this way, you will find words starting with the letter ‘U’ in the dictionary. This is how a binary search algorithm works.

Binary Search

Binary search is an efficient searching algorithm with only the requirement that the elements in the array are sorted already.

It is a great implementation of the divide and conquer algorithm technique. It divides the array at the middle and then selects the first or the second half based on the search element and then repeats the process with the selected half until the search element is found (or not).

1. Works on the Divide and conquer technique to search for the elements.
2. Efficient than linear search algorithm.

Working of Binary Search

Objective: Search of element ‘73’ in the below array

Step 1: Find the middle element.
mid = low + (high – low) / 2

Step 2: Select the second half by changing low to mid+1.
low=mid+1

Step 3: Repeat steps 1 and 2 until the element is found.

The element found at location 8.

Pseudocode for Binary Search

Procedure binary_search
   Arr ← sorted array
   len ← size of the array
   se ← search element

   Set low = 1
   Set high = len

   while se not found
      if high < low 
         EXIT: se does not exist.
   
      set mid = low + ( high - low ) / 2
      
      if Arr[mid] < se
         set low = mid + 1
         
      if Arr[mid] > se
         set high = mid- 1 

      if Arr[mid] = se 
         EXIT: se found at mid
   end while
   
end procedure

Algorithm for Binary Search

1. Iterative approach for Binary Search

Step 1: set low = starting_index, high = last_index, loc = - 1
Step 2: repeat steps 3 and 4 while low <= high
Step 3: set mid = (low + high)/2
Step 4: if Arr[mid] = se
             set loc = mid
             print “ search element is present at location: “ + loc
             go to step 6
             else if Arr[mid] < se
             set low = mid + 1
             else
             set high = mid - 1
             [end of if]
             [end of loop]
step 5: if loc = -1
             print "search element is not present in the array"
             [end of if]
step 6: Stop

2. Recursive approach for Binary Search

BinarySearch(arr, se, low, high)
        mid = (low + high) / 2 
        if se == arr[mid]
            return mid
        else if se > arr[mid]       
            return BinarySearch(arr, se, mid + 1, high)
        else                               
            return BinarySearch(arr, se, low, mid - 1)

Binary Search Recursive implementation in C

#include <stdio.h>
int binarySearch(int arr[], int low, int high, int se)
{
    if (high >= low) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == se)
            return mid;
        if (arr[mid] > se)
            return binarySearch(arr, low, mid - 1, se);
        return binarySearch(arr, mid + 1, high, se);
    }
    return -1;
}
 
int main(void)
{
    int arr[] = { 7, 18, 26, 38, 42,57,61,73,84,91 };
    int len = sizeof(arr) / sizeof(arr[0]);
    int searchelement = 73;
    int result = binarySearch(arr, 0, len - 1, searchelement);
    if(result == -1) 
    printf("Element is not present in array");
    else
    printf("Element is present at location:  %d ",result+1);
    return 0;
}

Recursive implementation of Binary Search in C++

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int arr[], int low, int high, int se)
{
    if (high >= low) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == se)
            return mid;
 
        if (arr[mid] > se)
            return binarySearch(arr, low, mid - 1, se);
 
        return binarySearch(arr, mid + 1, high, se);
    }
    return -1;
}
 
int main(void)
{
    int arr[] = { 7, 18, 26, 38, 42,57,61,73,84,91 };
    int searchelement = 73;
    int len = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, 0, len - 1, searchelement);
    if(result == -1) 
    cout << "Element is not present in array" ;
    else
    cout << "Element is present at location: " << result+1;
    return 0;
}

Binary Search Recursive implementation in Java

public class BinarySearch {
    
    int binarySearch(int arr[], int low, int high, int se)
    {
        if (high >= low) {
            int mid = low + (high - low) / 2;
            
            if (arr[mid] == se)
                return mid;
 
            if (arr[mid] > se)
                return binarySearch(arr, low, mid - 1, se);

            return binarySearch(arr, mid + 1, high, se);
        }
        return -1;
    }
 
    public static void main(String args[])
    {
        BinarySearch ob = new BinarySearch();
        int arr[] = { 7, 18, 26, 38, 42,57,61,73,84,91 };
        int len = arr.length;
        int searchelement = 73;
        int result = ob.binarySearch(arr, 0, len - 1, searchelement);
        if (result == -1)
            System.out.println("Element not present");
        else
            System.out.println("Element found at location: " + result+1);
    }
}

Recursive implementation of Binary Search in Python

def binarySearch (arr, low,high, se):
 
    if high >= low:
 
        mid = low + (high - low) // 2
 
        if arr[mid] == se:
            return mid
         
        elif arr[mid] > se:
            return binarySearch(arr, low, mid-1, se)
 
        else:
            return binarySearch(arr, mid + 1, high, se)
 
    else:
        return -1
 
arr = [ 7, 18, 26, 38, 42,57,61,73,84,91 ]
searchelement = 73
 
result = binarySearch(arr, 0, len(arr)-1, searchelement)
 
if result != -1:
    print ("Element is present at location % d" % (result+1))
else:
    print ("Element is not present in array")

Binary Search Iterative implementation in C

#include <stdio.h>
 
int binarySearch(int arr[], int low, int high, int se)
{
    while (low <= high) {
        int mid = low + (high - low) / 2;
 
        if (arr[mid] == se)
            return mid;
 
        if (arr[mid] < se)
            low = mid + 1;
 
        else
            high = mid - 1;
    }
 
    return -1;
}
 
int main(void)
{
    int arr[] = {7, 18, 26, 38, 42,57,61,73,84,91 };
    int len = sizeof(arr) / sizeof(arr[0]);
    int searchelement = 73;
    int result = binarySearch(arr, 0, len - 1, searchelement);
    if(result == -1)
    printf("Element is not present");
    else
    printf("Element present at location: %d",result+1);
    return 0;
}

Iterative implementation of Binary Search in C++

#include <bits/stdc++.h>
using namespace std;
 
int binarySearch(int arr[], int low, int high, int se)
{
    while (low <= high) {
        int mid = low + (high - low) / 2;
 
        if (arr[mid] == se)
            return mid;
 
        if (arr[mid] < se)
            low = mid + 1;
 
        else
            high = mid - 1;
    }
 
    return -1;
}
 
int main(void)
{
    int arr[] = {7, 18, 26, 38, 42,57,61,73,84,91 };
    int len = sizeof(arr) / sizeof(arr[0]);
    int searchelement = 73;
    int result = binarySearch(arr, 0, len - 1, searchelement);
    if(result == -1)
    cout << "Element is not present" ;
    else
    cout << "Element present at index " << result+1;
    return 0;
}

Iterative implementation of Binary Search in Java

public class BinarySearch {

    int binarySearch(int arr[], int se)
    {
        int low = 0, high = arr.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
 
            if (arr[mid] == se)
                return mid;
 
            if (arr[mid] < se)
                low = mid + 1;
 
            else
                high = mid - 1;
        }
 
        return -1;
    }
 
    public static void main(String args[])
    {
        BinarySearch ob = new BinarySearch();
        int arr[] = { 7, 18, 26, 38, 42,57,61,73,84,91 };
        int searchelement = 73;
        int result = ob.binarySearch(arr, searchelement);
        if (result == -1)
            System.out.println("Element not present");
        else
            System.out.println("Element present at location: " + (result+1));
    }
}

Binary Search Iterative implementation in Python

def binarySearch(arr, low, high, se):
 
    while low <= high:
 
        mid = low + (high - low) // 2;
       
        if arr[mid] == se:
            return mid
 
        elif arr[mid] < se:
            low = mid + 1
 
        else:
            high = mid - 1
  
    return -1
 
arr = [ 7, 18, 26, 38, 42,57,61,73,84,91 ]
searchelement = 73
 
result = binarySearch(arr, 0, len(arr)-1, searchelement)
 
if result != -1:
    print ("Element present at location: % d" % (result+1))
else:
    print ("Element is not present in array")

Complexity of Binary Search

The best-case scenario for binary search is when the search element is present at the middle location in the first iteration only.

Linear search vs Binary search

Applications of Binary Search

1. It is used in libraries of programming languages like JAVA, .Net, and C++
2. It is used to pinpoint the place of error during debugging.

Conclusion

Binary search is a faster, efficient, and widely used algorithm for searching in a dataset. We have seen the working of binary search and its implementation in this article.

Binary search is usually preferred for large inputs and unknowingly used by us in daily life. For example, searching for a roll number in a university database can be efficiently done by binary search.