Binary Search Algorithm (With Code)

# Binary Search Algorithm (With Code)

Updated on May 11, 2022 17:39 IST

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:

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 :
");
scanf("	 %d",& n);
printf("
Mention the %d elements :
", n);
for ( i = 0 ; i < n ; i++ )
scanf(" 	 %d",&arr[i]);
printf("Mention the element you wish to find in the array :
");
scanf("	 %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
", find, mid);
break;
}
else
end = mid - 1;
mid = (begin + end)/2;
}
if ( begin > end )
", find);
return 0;
}```

## 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:
```

## 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.

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

## FAQs

Is recursive Binary Search better than iterative Binary search?

With regards to the time complexity both have the same complexity, i.e, O(logn). 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.

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

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.