Time and Space Complexity of Binary Search Explained
Basics of Python
5 Hrs. duration
9 Modules
1800+ Learners
Start Learning
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:
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
function bS(arr, target):
left = 0
right = length(arr) - 1
//Run a while-loop
while left <= right:
mid = left + (right - left) / 2
if arr[mid] == target:
return mid // Target found, return index
else if arr[mid] < target:
left = mid + 1 // Ignore the left half
else:
right = mid - 1 // Ignore the right half
return -1 // Target not found
Let’s understand the workings of a binary search (iterative) algorithm with the help of a code example in C++.
Example:
#include <iostream>
using namespace std;
// Binary search function
int bS(int arr[], int size, int target) {
int left = 0;
int right = size - 1;
while (left <= right) {
// Find the middle index
int mid = left + (right - left) / 2;
// Check if the target element is at the mid
if (arr[mid] == target)
return mid;
// If the target element is greater, ignore the left half
if (arr[mid] < target)
left = mid + 1;
// If the target element is smaller, ignore the right half
else
right = mid - 1;
}
// Target element was not found
return -1;
}
// Main function
int main() {
int nums[] = {33, 44, 50, 55, 66, 77, 88};
int size = sizeof(nums) / sizeof(nums[0]);
int target = 50;
int res = bS(nums, size, target);
if (res != -1)
cout << "The target element found at index: " << res << endl;
else
cout << "The target element not found in the array" << endl;
return 0;
}
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?
The starting length of the array is n.
Iteration Reduction:
First iteration: After the first comparison, the size of the search space is reduced to n / 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.
Kth Iteration: After k iterations, the size of the search space is n / 2^k.
Convergence to a Single Element:
The process continues until the search space is narrowed down to a single element, where n / 2^k = 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)
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.
FAQs
What is the time complexity of Binary Search in the best case?
When the target element is located in the middle of the array on the first comparison, the binary search's best-case time complexity is O(1).
What is the time complexity of BST?
In a balanced Binary Search Tree (BST), the temporal complexity of basic operations (search, insertion, and deletion) is O(log n). It can degenerate to O(n) in an unbalanced BST.
Why is binary search time complexity O(log n)?
The search space is repeatedly cut in half via binary search, which results in O(log n), the logarithmic number of comparisons.
Is Binary Search a divide-and-conquer technique?
Yes, it is a divide-and-conquer technique as a binary search breaks the problem down into smaller subproblems.
Is Binary Search better than linear search?
In sorted arrays, binary search is indeed more efficient than linear search, with an O(log n) time complexity as compared to O(n).
Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.