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

Selectcaret down icon
Select Area of interestcaret down icon
Select Work Experiencecaret 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

45+ Best Machine Learning Project Ideas For Beginners [2024]
329940
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

21 May 2024

Top 15 IoT Interview Questions &#038; Answers 2024 – For Beginners &#038; Experienced
64851
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

19 May 2024

40 Best IoT Project Ideas &#038; Topics For Beginners 2024 [Latest]
765532
In this article, you will learn the 40Exciting IoT Project Ideas & Topics. Take a glimpse at the project ideas listed below. Best Simple IoT Proje
Read More

by Kechit Goyal

19 May 2024

Top 22 Artificial Intelligence Project Ideas &#038; Topics for Beginners [2024]
415054
In this article, you will learn the 22 AI project ideas & Topics. Take a glimpse below. Best AI Project Ideas & Topics Predict Housing Price
Read More

by Pavan Vadapalli

18 May 2024

Image Segmentation Techniques [Step By Step Implementation]
64018
What do you see first when you look at your selfie? Your face, right? You can spot your face because your brain is capable of identifying your face an
Read More

by Pavan Vadapalli

16 May 2024

6 Types of Regression Models in Machine Learning You Should Know About
283412
Introduction Linear regression and logistic regression are two types of regression analysis techniques that are used to solve the regression problem
Read More

by Pavan Vadapalli

16 May 2024

How to Make a Chatbot in Python Step By Step [With Source Code]
31269
Creating a chatbot in Python is an essential skill for modern developers looking to enhance user interaction and automate responses within application
Read More

by Kechit Goyal

13 May 2024

Artificial Intelligence course fees
5802
Artificial intelligence (AI) was one of the most used words in 2023, which emphasizes how important and widespread this technology has become. If you
Read More

by venkatesh Rajanala

29 Feb 2024

Artificial Intelligence in Banking 2024: Examples &#038; Challenges
6686
Introduction Millennials and their changing preferences have led to a wide-scale disruption of daily processes in many industries and a simultaneous g
Read More

by Pavan Vadapalli

27 Feb 2024

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