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