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’,

1. Set lower_bound L = 0 and upper_bound U to N-1
2. 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
3. If L > R
   1. The element X is not present in the given array Arr
4. 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).

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.

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.

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.