Binary Search Algorithm (With Code)

In our day-to-day life, we all tend to search for different queries. The binary search algorithm is one of the popular searches used to find an element in an array in the computer science world of data structures.

 

In this article on the Binary Search algorithm, let us understand the following pointers:

• Understanding Binary Search Algorithm
• Binary Search Example
• Implementing Binary Search in C
• Implementing Binary Search in Python
• Time & Space Complexity of Binary Search
• Top Interview Questions on Binary Search

So, let us get started by understanding what the Binary Seach algorithm is.

What is Binary Search Algorithm?

Binary Search, also known as half-interval search is one of the most popular search techniques to find elements in a sorted array. Here, you have to make sure that the array is sorted.

The algorithm follows the divide and conquer approach, where the complete array is divided into two halves and the element to be searched is compared with the middle element of the list. If the element to be searched is less than the middle element, then the search is narrowed down to 1st half of the array. Else, the search continues to the second half of the list.

Algorithm:

Before we understand the algorithm, refer below to understand the steps involved:

• Consider a key element you wish to search. 
• Compare the key element with the middle element
• If the element you wish to search matches with the middle element, then return the index of the middle element.
• Else if the element you wish to search is greater than the middle element, then the key element can only lie on the right-hand side of the middle element. Then, you have to recur the right half of the sub-array.
• Else if the element you wish to search is less than the middle element, then you have to recur the left half.

Now, that you have understood the workflow of Binary Search, refer below to understand the algorithm.

Here, lets us assume exarr is an array of n elements, and left, middle and right are used to find the element “key”.

BinarySearch (exarr, key)
Left = 0
Right = exarr(n -1)   
While left < =right
 Middle = (left + right )/2
If exarr[middle] < key then
Left = middle + 1
Else if exarr[middle] > key
Right = middle - 1
Else
Return middle

Now, let us understand the same with a simple example.

Binary Search Example

Consider the following array and the search element to understand the Binary Search techniques.

Array considered: 09 17 25 34 49

Element to be searched: 34

Step 1: Start the Binary Search algorithm by using the formula middle = (left + right )/2 Here, left = 0 and right = 4. So the middle will be 2. This means 25 is the middle element of the array.

Step 2: Now, you have to compare 25 with our seach element i.e. 34. Since 25 < 34, left = middle + 1 and right = 4.

Step 3: So, the new middle = (3 + 4)/ 2, which is 3.5 considered as 3.

Step 4: Now, If you observe, the element to be searched = middle found in the previous step. This implies that the element is found at a[3].

Binary Search  in C 

Implementation of Binary Search can be done in the following way:

// Binary Search
 
#include<stdio.h>
#include<stdlib.h>
 
int main()
{
    int i, begin, end, mid, n, find, arr[100];
    printf("Mention the number of elements in the array : \n");
    scanf("\t %d",& n);
    printf("\n Mention the %d elements : \n", n);
    for ( i = 0 ; i < n ; i++ )
        scanf(" \t %d",&arr[i]);
    printf("Mention the element you wish to find in the array : \n");
    scanf("\t %d",&find);
    begin = 0;
    end = n - 1;
    mid = (begin+end)/2;
    while( begin <= end )
    {
        if ( arr[mid] < find )
            begin = mid + 1;
        else if ( arr[mid] == find )
        {
            printf("%d is found at the location %d, in the array\n", find, mid);
            break;
        }
        else
            end = mid - 1;
        mid = (begin + end)/2;
    }
    if ( begin > end )
        printf(" Sorry! %d is not found in the list.\n", find);
    return 0;
}

Output:

Binary Search in Python

Binary Search can be implemented in the Python programming language, in the following way:

def BiSearch(exarr, left, right, find):
    if right >= left:
        middle = left + (right - left) // 2
 
        # If element is present at the middle element
        if exarr[middle] == find:
            return middle
 
        # If element is less than middle, then element is present at LHS
        elif exarr[middle] > find:
            return BiSearch(exarr, left, middle-1, find)
 
        # Else element is present at RHS
        else:
            return BiSearch(exarr, middle + 1, right, find)
 
    else:
        # Element is not present in the exarray
        return -1
 
 
# Take Users Input
m=int(input("Mention the number of elements in the array : "))
exarr=list(map(int, input(" Enter the elements of the array : ").strip().split()))
 
#enter the element to be found    
find = int(input("Mention the element you wish to find in the array : "))
 
output =  BiSearch(exarr, 0, len(exarr)-1, find)
 
if output != -1:
    print("Element is found at index % d" % output)
else:
    print("Sorry! Element is not found in the array")

Output:

Time & Space Complexity of Binary Search

Time Complexity

Scenario	Complexity	Comments
Best Case	O(1)	Occurs when the element to be searched is found in the 1st comparison itself.  So, the middle element itself is the key element.
Worst Case	O(log n)	Occurs when we continuously have to iterate the loop and reduce the space to find the key element.

Space Complexity

O(1) is the space complexity of the binary search.

Finally, let us take a look at the most asked questions on Binary Search.

Top Interview Questions on Binary Search

Q1. What is the difference between Linear & Binary Search?

Ans.

Linear Search	Binary Search
Sequential access to data	Random access to data
The list need not be sorted	Requires list to be sorted
Uses equality (=) comparison only	Uses ordering comparisons like > / <
Has the complexity of O(n)	Has the complexity of O(log n)

Q2. Is recursive Binary Search better than iterative Binary search?

Ans. With regards to the time complexity both have the same complexity, i.e, O(log n). But, with respect to the space complexity, the iterative approach is better than the recursive approach.

The iterative approach allocates a constant space of O(1) for the function call, whereas the recursive approach follows the tail recursion by using a stack function. This implies that the result is calculated before the recursion call is made, implying no requirement of the stack to store the intermediate value, as it moves to the next recursive call.

Q3. Why do we round down the average while finding the middle element of the list?

Ans. Rounding the average to a lower/ upper limit does not matter, as, at the end of the day, you are going to divide the list in half and find the search element.

With this, we end this article on Binary Search Algorithm and how to implement it. We hope you found it informative.

Top Trending Tech Articles:
Career Opportunities after BTech | Online Python Compiler | What is Coding | Queue Data Structure | Top Programming Language | Trending DevOps Tools | Highest Paid IT Jobs | Most In Demand IT Skills | Networking Interview Questions | Features of Java | Basic Linux Commands | Amazon Interview Questions

Recently completed any professional course/certification from the market? Tell us what liked or disliked in the course for more curated content.

Click here to submit its review with Shiksha Online.