Blog_Banner_Asset
    Homebreadcumb forward arrow iconBlogbreadcumb forward arrow iconArtificial Intelligencebreadcumb forward arrow iconTime and Space Complexity of Binary Search Explained

Time and Space Complexity of Binary Search Explained

Last updated:
23rd Apr, 2023
Views
Read Time
8 Mins
share image icon
In this article
Chevron in toc
View All
Time and Space Complexity of Binary Search Explained

Introduction to Binary Search Algorithm

Binary search, also known as half-interval or logarithmic search, is a search algorithm to find the position of an element in a sorted array. It works by repeatedly dividing the array in half based on the middle element of the array. This is done until the middle element is equal to the value to be searched or the array can no longer be divided, in case the search value is not present in the input array.

The binary search runs in logarithmic time in the worst case and is faster than linear search algorithms in most scenarios. However, unlike linear search, it can only be applied to sorted arrays. Binary search is a versatile algorithm with many variations for specific use cases. It can also find an array’s closest (next smallest or largest) value relative to the search value when absent.

Let us go through the binary search algorithm for a given sorted array ‘Arr having ‘N’ elements and a search value ‘X’,

 

Ads of upGrad blog
  1. Set lower_bound L = 0 and upper_bound U to N-1

 

  1. Repeat until L <= R
    1. Calculate middle M as the floor of (L+U)/2
    2. If Arr[M] > X, Set L to M + 1
    3. Else if Arr[M] < X, Set U to M – 1
    4. Else, Break out of the loop as Arr[M] = X

 

  1. If L > R
    1. The element X is not present in the given array Arr

 

  1. Else
    1. The loop in step 2. was broken out from, and the element X is present at position M.

 

The algorithm gets the input sorted array and keeps track of the array’s lower bound L and upper bound U to be searched. Within each iteration of step 2., the value of the middle M is determined, and L or U is updated ( L to M + 1 if Arr[M] > X or U to M – 1 if Arr[M] < X ), effectively reducing the size of the array to be searched to half. The is repeated till Arr[M] = X when the loop is exited with the search value at index M, or the array cannot be divided further because the lower bound is greater than the upper bound.

In order to further gain an understanding of the concept, you can also enrol in upGrad’s Master of Science in Machine Learning & AI from LJMU program.

Understanding the Big O Notation

Big O notation is used to measure the efficiency of an algorithm. It is used to evaluate how the space or run time requirement grows with the growth of its input size. It is often good practice for developers to understand the big O notation and its significance in writing efficient and cost-effective algorithms. The letter O was chosen because this is also referred to as the function’s order. Formally defined, Big O notation can be referred to as an asymptotic notation that sets out the limiting behaviour of a function when the argument inclines towards a specific value or infinity. 

Similar to big O notation, several associated notations use the signs o, Ω, ω, and Θ to identify diverse asymptotic growth rates.

Join Artificial Intelligence 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.

Time Complexity Analysis of Binary Search

Besides gaining an in-depth understanding of binary search through upGrad’s Executive PG Program in Machine Learning & AI from IIITB, you can explore the concept of binary search through the best and worst-case binary search time complexity. 

Best case time complexity of Binary Search


The best binary search occurs when the search element is at the middle index. In that case, the element is found in the first iteration of the algorithm, and the search is completed. Therefore, Binary search has a best-case time complexity of O(1).

Average case time complexity of Binary Search

There are two scenarios we need to consider,

  1. The search value is present in the array between index 0 to N-1 (N scenarios)
  2. The search value is not present in the array (1 scenario) 

So there are N + 1 cases that we need to take into consideration.

The first iteration of the algorithm returns an element at N/2.

The second iteration returns elements at N/4 or 3N/4 (If the right half is removed, then N/4, otherwise 3N/4).

The third iteration returns elements at N/8, 3N/8, 5N/8, 7N/8, and so on.

As can be seen that each iteration can scan 2t-1 elements

We already know that there can be, at most, log N iterations. So ‘t’ can vary from 0 to log N.

Total comparisons that occur = 1 * (Elements requiring one comparison) + 2 * (Elements requiring two comparisons) + … + log N * (Elements requiring log N comparisons)


Total comparisons that occur = 1 * 1 + 2 * 2 + 3 * 4 + … log N * ( 2log N – 1)

Total comparisons that occur = 1 + 2 + 12 + …. log N * ( 2log N – 1) = 2log N * (log N – 1) + 1

Total comparisons that occur (A) = N * (log N – 1) + 1 

the total number of cases (B) = N + 1

Therefore, the average number of comparisons (A/B) = (N * (log N – 1) + 1) / (N + 1)

the average number of comparisons = (N * log N) / (N + 1) – N / (N + 1) + 1 / (N + 1)

Picking the dominant term (N * log N) / (N + 1), which is of the order of log N, we can conclude that the average case time complexity of Binary Search is O(log N).


Worst case time complexity of Binary Search


The worst case for binary search occurs when the search element is at the first or last index (smallest or largest element in the array). 

Let’s take the case of the largest element. In this case, the left half of the array is repeatedly removed until the only remaining element is the largest (rightmost) element. As discussed in the previous section, the maximum iterations for an input array of size ‘N’ is logN and hence the worst-case time complexity of Binary search is O(log N).

Best Machine Learning and AI Courses Online

Space Complexity of Binary Search Algorithm

The space complexity of an algorithm is the extent of the growth of storage space required as the input size grows. This refers to the memory used by variables in the algorithm. Although space and time complexity are unrelated, it is important to remember that reducing the space complexity will make the algorithm run faster.

In the Binary Search algorithm, we only keep track of the lower bound, upper bound and middle elements. As these variables can be reused and no new variable needs to be created in the memory on each iteration, the space requirement is a constant. This means that the Binary Search algorithm has a space complexity of O (1).

Comparing Binary Search with Other Searching Algorithms

Different search algorithms are used in different scenarios. Some algorithms won’t work on input data, while some would be quicker than others on the same input. 

The Binary Search is much quicker than a linear search algorithm because the data that needs to be searched is halved on each run vs sequential processing where every element needs to be scanned (O (logN) vs O(n)). So, to search through 1024 values, you could do it in, at most, ten iterations compared to 1024 of linear search. The only problem with Binary search is that it needs to be run on sorted input data, and it is not feasible to perform a sort just for searching as they are much more complex algorithms.

Ads of upGrad blog

Interpolation search is a variation of the Binary Search. The only difference is that instead of always checking the middle element for the given lower and upper bounds, the interpolation search goes to different locations based on the searched value. This algorithm also requires sorting the input array and the data uniformly distributed.

Trending Machine Learning Skills

Applications of Binary Search

Dictionaries

A dictionary contains thousands of words sorted alphabetically. To search for a given word, it would be time-consuming to look word by word. Using binary search to search for the word ‘Target’, we can go to the middle page and compare the word there with the word ‘Target’. If it is alphabetically larger, we can ignore all the pages to the right of the middle pages, or if its alphabetically smaller, we can ignore all pages to the left and continue the same process until we find the page of our search word.

Resource management

For large systems, it is possible to make factual estimations of the resources required to run smoothly. Developers can run load tests with different resource configurations and approximately determine the required configuration for it to run without any issues.

Conclusion

Binary search is an important concept for anyone who wants to understand the complexities of artificial intelligence. To further grasp proficiency in this dynamic field, you can enrol in upGrad’s Executive PG Program in Data Science & Machine Learning from the University of Maryland. The course will cover topics like Deep Learning, Statistical Analysis, NLP, and more to keep you abreast of the changing AI domain. Along with expert guidance, practical experience with capstone projects will further help you shape a career within this evolving field. 

Profile

Pavan Vadapalli

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 Coursecaret down icon
Selectcaret down icon
By clicking 'Submit' you Agree to  
UpGrad's Terms & Conditions

Our Popular Machine Learning Course

Frequently Asked Questions (FAQs)

1What is the time complexity of binary search on a sorted array?

The time complexity of binary search on a sorted array is O(log N), where N refers to the number of elements present in the array. Binary search efficiently cuts down the search space by half at each step, resulting in logarithmic time complexity.

2Is the time complexity of binary search affected by the size of the array?

Yes, the time complexity of binary search can be influenced by the size of its array. Binary search has a logarithmic time complexity, which means it scales well with larger arrays. As the array size increases, so does the iterations required.

3Can binary search have a space complexity of O(log N)?

No, binary search does not contain a space complexity of O(log N). The space complexity continues to be O(1) as the input size grows.

Explore Free Courses

Suggested Blogs

Top 10 Deep Learning Interview Questions &amp; Answers
5555
Although still evolving, Deep Learning has emerged as a breakthrough technology in the field of Data Science. From Google’s DeepMind to self-dri
Read More

by Prashant Kathuria

21 Sep 2023

Top 8 Exciting AWS Projects &#038; Ideas For Beginners [2023]
86637
AWS Projects & Topics Looking for AWS project ideas? Then you’ve come to the right place because, in this article, we’ve shared multiple AWS proj
Read More

by Pavan Vadapalli

19 Sep 2023

Data Preprocessing in Machine Learning: 7 Easy Steps To Follow
126944
Summary: In this article, you will learn about data preprocessing in Machine Learning: 7 easy steps to follow. Acquire the dataset Import all the cr
Read More

by Kechit Goyal

18 Sep 2023

Top 15 IoT Interview Questions &#038; Answers 2023 – For Beginners &#038; Experienced
61726
These days, the minute you indulge in any technology-oriented discussion, interview questions on cloud computing come up in some form or the other. Th
Read More

by Kechit Goyal

15 Sep 2023

45+ Interesting Machine Learning Project Ideas For Beginners [2023]
302343
Summary: In this Article, you will learn Stock Prices Predictor Sports Predictor Develop A Sentiment Analyzer Enhance Healthcare Prepare ML Algorith
Read More

by Jaideep Khare

14 Sep 2023

Why GPUs for Machine Learning? Ultimate Guide
5000
In the realm of modern technology, the convergence of data and algorithms has paved the way for groundbreaking advancements in artificial intelligence
Read More

by Pavan Vadapalli

14 Sep 2023

How to Implement Machine Learning Steps: A Complete Guide
5000
The technology landscape is undergoing a profound shift, primarily attributed to the transformative force of machine learning. This groundbreaking tec
Read More

by Pavan Vadapalli

13 Sep 2023

25 Machine Learning Interview Questions &#038; Answers &#8211; Linear Regression
40524
Introduction Machine Learning Interviews can vary according to the types or categories, for instance, a few recruiters ask many Linear Regression int
Read More

by Thulasiram Gunipati

10 Sep 2023

13 Interesting Neural Network Project Ideas &#038; Topics for Beginners [2023]
4775
The topic of neural networks has captivated the world of artificial intelligence and machine learning with its ability to mimic the human brain’
Read More

by Pavan Vadapalli

07 Sep 2023

Schedule 1:1 free counsellingTalk to Career Expert
icon
footer sticky close icon