Binary Search Algorithm & Time Complexity [2024]

# Binary Search Algorithm & Time Complexity [2024]

Last updated:
30th Jan, 2022
Views
7 Mins
View All

In programming languages, we search arrays by implementing two methods — Linear Search and Binary Search. Searching simply refers to finding a specific element from a list of elements linked to an array.

Linear search involves sequentially checking every element of a given list repeatedly until the element in question is found, or the algorithm is through with the list. On the other hand, binary search works by dividing a given list into two halves and comparing each item to the list’s middle element. Both algorithms are essential aspects of programming where arrays are concerned. However, binary search is more time-efficient and easily executable when we have a sorted list.

This post aims to paint a clear picture of binary search and its time complexity with respect to different cases.

## What is Binary Search?

Binary search is one of the more commonly used techniques for searching data in arrays. You can also use it for sorting arrays. The principle of binary search is straightforward. It repeatedly divides the elements of an array into two halves with every iteration. The search logic checks whether the specified value is less than the middle item of the array and accordingly ignores the half in which the value is not present. This process happens in a loop until the correct value is located. Here are the steps involved in the binary search:

1. Comparing the given item with the middle item of the array.
2. If it matches with the middle element, then the program returns the middle element as the answer.
3. If the unknown element is lesser than the middle element, we search the left half.
4. If the unknown element is greater than the middle element, search the right half.
5. This entire cycle repeats until we find the wanted element.

It should be noted that the user needs to sort the address before searching any element for accurate results.

Binary search, in practice, is more efficient than linear search. However, one needs to specify the order in which division of the array will occur.

## What are the Different Types of Binary Search?

Binary search can be implemented in two ways based on the space complexity of the binary search algorithm:

• Recursive Binary Search
• Iterative Binary Search

## Recursive Binary Search

In this method, there are no iterations or loops used to control the flow of the program. The maximum and minimum values are utilized as the boundary conditions.

The space complexity of this method is O(log n).

Here is a code snippet for a recursive binary search using C

#include <stdio.h>

int binary_Search(int array[], int x, int start, int end)

{

if (end >= start)

{

int midIndex = start + (end – start) / 2;

if (array[midIndex] == x)

return midIndex;

if (array[midIndex] < x)

return binary_Search(array, x, start, midIndex – 1);

return binary_Search(array, x, midIndex + 1, end);

}

return -1;

}

int main(void)

{

int array[] = {21, 45, 56, 6, 17, 28, 95};

int n = sizeof(array) / sizeof(array[0]);

int x = 45;

int answer = binary_Search(array, x, 0, n – 1);

if (answer == -1)

printf(“Element not present”);

else

return 0;

}

Output:

## Iterative Binary Search

In this method, a loop is employed to control the iterations.

The space complexity is O(1) for the iterative binary search method.

Here is a code snippet for an iterative binary search using C:

#include <stdio.h>

int Binary_Search( int array[], int x, int start, int end)

{

while (start <= end) {

int midIndex = start + (end – start) / 2;

if (array[midIndex] == x)

return midIndex;

if (array[midIndex] > x)

start = midIndex + 1;

else

end = midIndex – 1;

}

return -1;

}

int main(void) {

int array[] = {12, 35, 56, 15, 127, 85, 17};

int n = sizeof(array) / sizeof(array[0]);

int x = 45;

int answer = Binary_Search(array, x, 0, n – 1);

if (answer == -1)

printf(“Element not present”);

else

return 0;

}

Output:

Answer: “Element is not present”

## Dry run of Binary Search Algorithm

Item to be searched is 7

 0 1 2 3 4 7 21 37 45 58

beg=0, end=4, mid=2

 0 1 2 3 4 7 21 37 45 58

beg=0, end=1, mid=0

 0 1 2 3 4 7 21 37 45 58

Element is found at index 0. Therefore, 0 will get returned.

## What is Binary Search Time Complexity?

There are three-time complexities for binary search:

1. O(1) – O(1) means that the program needs constant time to perform a particular operation like finding an element in constant time, as it happens in the case of a dictionary.
2. O(n) – O(n)  means that the time depends on the value of n. it is directly proportional to the operation’s duration of searching an element in the array of n elements.
3. O(log n) – O(log n) is used in cases where we use recursive functions. The time complexity is dependent on the number of times the loop runs until it breaks. Unlike the previous one, it is not reliant on n but dependent upon the number of times the loop operates.

Here’s an understanding of binary search time complexity in detail:

 Cases Time Complexity Best Case: the result is returned in the first iteration O(1) Average Case: the result is returned in three/four/average number of  iterations O(logn) Worst Case: the result is produced at the last comparison O(logn)

## Best Case Time Complexity

The best time complexity of binary search occurs when the required element is found in the first comparison itself, and only one iteration occurs. Therefore we use O(1). Essentially for this case, the element needs to be in the exact middle of the list because, in binary search, the first competition occurs with the middle element. Once the middle element does not return the correct answer, the iteration begins for the lesser half of the greater half.

## Average Case Time Complexity

Taking an example of n distinct numbers (s1, s2, s3, …..s(n-1), sn), there can be two scenarios:

• Required element is present between index 0 to (n-1).
• Required element is not present in the given list from index 0 to (n-1).

So, there are n+1 separate cases that we need to take into consideration.

If the required element is present in index Y, then the program performing Binary Search will perform Y+1 comparisons, as:

The element at index n/2 returns in the first comparison (as Binary Search starts from the middle element, as in the case of Best time complexity).

Similarly, the 2nd comparison returns the elements at index n/4 and 3n/4 since their outcomes are based on the result of the 1st comparison.

According to this, we can conclude:

• Elements that need 1 comparison: 1
• Elements that need 2 comparisons: 2
• Elements that need 3 comparisons: 4

Therefore, elements that need t comparisons: 2^(t-1)

The maximum number of iterations = (Number of times n is divided by 2 so that result is 1) = logN comparisons.

t can vary from 0 to logn.

Total comparisons occuring = 1 * (Elements that need 1 comparison) + 2 * (Elements that need 2 comparisons) + … + logn * (Elements that need log n comparisons)

Total comparisons occuring = 1 * (1) + 2 * (2) + 3 * (4) + … + logn * (2^(logn-1))

Total comparisons occuring = 1 + 4 + 12 + 32 + … = 2^logn* (logn – 1) + 1

Total comparisons occuring = n * (logn – 1) + 1

Total number of cases = n+1

Therefore, average number of comparisons = (n*(logn-1)+1) / (n+1)

Average number of comparisons = n * logn / (n+1) – n/(n+1) + 1/(n+1)

The dominant term is n* logn / (n+1), which is approximately logn.

Thus, we can conclude that the average case Time Complexity of Binary Search is O(logN).

## Worst Case Time Complexity

The worst time complexity of binary search occurs when the element is found in the very first index or the very last index of the array. For this scenario, the number of comparisons and iterations required is logn, where n is the number of elements in the array. It is called the worst time complexity because it consumes a lot of time for large arrays containing hundreds and thousands of values. Accordingly, hundreds and thousands of iterations must occur.

## Conclusion

With global digitization scaling rapidly, learning programming languages is the need of the hour. Binary search is a pivotal tool that finds its usage in programming across languages. With a clear understanding of how these searches occur and the related load on the compiler, developers can write easily-executable codes such that the project does not encounter any bugs. Thus, understanding binary search complexities is a foundation stone for anyone looking forward to improving their coding skills.

We hope this post has provided a clear understanding of the same.

If you’d like to learn about binary search tree time complexities, join upGrad’s 20-months Master of Science in Machine Learning & Artificial Intelligence offered in collaboration with IIIT Bangalore & LJMU. The program syllabus is curated by reputed faculty and industry experts and includes 25+ mentorship sessions, 12+ industry projects, and 6 capstone projects, as well as 360-degree career support. Students get access to top global job opportunities on completion of the course.

Learn Machine Learning courses online from the World’s top Universities – Masters, Executive Post Graduate Programs, and Advanced Certificate Program in ML & AI to fast-track your career.

Go ahead and book your seat today!

Blog Author
Director of Engineering @ upGrad. Motivated to leverage technology to solve problems. Seasoned leader for startups and fast moving orgs. Working on solving problems of scale and long term technology strategy.
Get Free Consultation

Select
Select Area of interest
Select Work Experience
By clicking 'Submit' you Agree to
UpGrad's Terms & Conditions

## Suggested Blogs

63211
Introduction As someone deeply immersed in the ever-changing landscape of technology, I’ve witnessed firsthand the rapid evolution of trending

23 Jan 2024

6375
A CNN (Convolutional Neural Network) is a type of deep learning neural network that uses a combination of convolutional and subsampling layers to lear

15 Apr 2023

5613
What is a Speech Recognition Software? Speech Recognition Software programs are computer programs that interpret human speech and convert it into tex

by Sriram

26 Feb 2023

6356
Artificial intelligence controls computers to resemble the decision-making and problem-solving competencies of a human brain. It works on tasks usuall

by Sriram

26 Feb 2023

5614
Taking on machine learning projects as a beginner is an excellent way to gain hands-on experience and develop a better understanding of the fundamenta

by Sriram

26 Feb 2023

5291
A CNN (Convolutional Neural Network) is a type of deep learning neural network that uses a combination of convolutional and subsampling layers to lear

by Sriram

26 Feb 2023

10850
IoT (Internet of Things) is a network that houses multiple smart devices connected to one Cloud source. This network can be regulated in several ways

by Sriram

25 Feb 2023

7818
Time complexity is a measure of the amount of time needed to execute an algorithm. It is a function of the algorithm’s input size and the type o

by Sriram

25 Feb 2023

11707
Machine learning can effectively analyze data with several dimensions. However, it becomes complex to develop relevant models as the number of dimensi