Time and Space Complexity of Binary Search Explained

Binary search is known as one of the most advanced searching algorithms and enjoys wide employment in the field of computers most especially when the retrieval of information must be efficiently done. No matter if it is searching a sorted array or maintaining complicated tree data structures, an abstract understanding of the time and space complexity of the binary search is of core importance to achieving results efficiently.

In this article, we will learn about the time and space complexity of binary search showing the efficiency of the technique, coding a practical example, learning time complexity in best, average, and worst case scenarios, and much more.

What is Binary Search?

Binary search is a search algorithm that uses the divide-and-conquer approach to search for a target element by reducing the search space into two halves recursively. More precisely, it is applied to those elements which are already sorted. Binary search cannot be applied to an unsorted array or list of elements. Rather than going through items one by one like in linear search, binary search reduces the search space by halving it with each iteration/recursion hence is more efficient.

How Binary Search Works

Binary search is a fundamental concept in algorithm design and problem-solving since it provides a great illustration of algorithm efficiency. Let’s briefly recap how binary search operates:

• Pre-condition: The array or data structure must be sorted.
• Algorithm:
  • Identify the middle element of the list or array.
  • Compare the middle element with the target element.
    • If the middle element is equal to the target element, we return its index.
    • If the target is smaller, search the left half i.e., all elements before the middle.
    • If the target is larger, search the right half i.e., all elements after the middle.
  • Repeat the process until the target is found or the search space gets empty.

Binary Search Pseudocode

Example:

Output:

Best Case

The best-case time complexity is said when the target element is found in the middle of the first iteration or recursive search. The time complexity in the best case for binary search is:

Time Complexity: O(1)

Why?

In the best case, the algorithm requires only one comparison, which happens when the middle element matches the target. This results in a constant-time complexity of O(1).

Worst Case

The worst-case scenario is said when the target element is either the largest or the smallest element in the sorted array, or when the search space is repeatedly divided in half until only one element remains. This occurs when the target element is missing from the collection or is at one of the farthest points. The time complexity in the worst case for binary search is:

Time Complexity: O(log n)

Why?

Binary search divides the search space in half for each iteration. The number of times you can halve an array with N entries in it until you are left with just one is log2(N). As a result, O(log N), where N is the array’s element count, represents the time complexity.

Average Case

The average-case time complexity is said when the target element is found in the middle of the array, but not always exactly in the middle.

Time Complexity: O(log n)

How?

1. The starting length of the array is n.
2. Iteration Reduction:
   1. First iteration: After the first comparison, the size of the search space is reduced to n / 2.
   2. Second iteration: After the second comparison, the size of the search space is n / 2^2, which simplifies to (n / 2) / 2 = n / 4.
   3. Kth Iteration: After k iterations, the size of the search space is n / 2^k.
3. Convergence to a Single Element:

The process continues until the search space is narrowed down to a single element, where n / 2^k = 1.

1. For k:

To find the number of iterations k needed to reduce the search space to one element, we set up the equation: n/2^k = 1

• Solving this equation for k, we multiply both sides by 2^k: n = 2^k
• Taking the logarithm base 2 of both sides gives: log2(n) = log2(2^k)
• Simplifying the right side: log2(n) = k * log2(2) = k

Therefore: k = log2(n)

1. The number of iterations k required to reduce the search space to one element, which is proportional to the logarithm of the array size, indicates that the average case time complexity of binary search is O(log n).

Space Complexity of Binary Search

Iterative Binary Search Space Complexity

In the iterative method, the space complexity is estimated by calculating the amount of additional space utilised. As binary search only requires pointer variables such as start, end and middle, it does not use any extra memory and, therefore, has a constant space complexity.

Space Complexity: O (1)

The amount of space utilised in the iterative version of the binary search does not vary with the input size. Only a constant extra space is required for the target element and index pointers.

Recursive Binary Search Space Complexity

In the recursive approach, each recursive call adds a new layer to the call stack. The level of recursion or recursion depth corresponds to how many times the area is narrowed or quartered or how many times the array is halved.

Space Complexity: O (log n)

Recursion depth of binary search is log n because at every stage the problem reduces by half. For every time this function is called recursively, space is used to hold the current state of the function being executed. In conclusion, the space complexity for the recursive approach is O (log n).

Binary Search on Different Data Structures

Binary search is not only used in Arrays but used in various other data structures like binary search trees, linked lists, etc.

Arrays

A binary search operates purely on the arrays. The only precondition for applying the binary search algorithm is that the array must be sorted. Binary search cannot be used on unsorted arrays in any way possible.

Binary Search Trees

The use of binary search is rather apparent even in BST, as nodes in the left subtree of the root comprise all elements lesser than the root, while nodes in the right subtree comprise all elements greater than the root. Searching in Balanced BST has the same Order of Growth which is O (log n).

Conclusion

In this article, we have learned about the complete details of time and space complexity of the binary search. We have covered the time complexity of binary search in best, worst, and average cases, and also the space complexity in iterative and recursive approaches.