Join Our 4-Week Free Gen AI Course with select Programs.

Request a callback

or Chat with us on

Time and Space Complexity of Binary Search Explained

Basics of Python
Basics of Python
icon
5 Hrs. duration
icon
9 Modules
icon
1800+ Learners
logo
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.

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

function bS(arr, target): left = 0 right = length(arr) - 1 &nbsp; //Run a while-loop while left <= right: mid = left + (right - left) / 2 &nbsp; 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 &nbsp; 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; }

Output:

The target element found at index: 2
DevOps & Cloud Engineering
Internship Assurance
DevOps & Cloud Engineering

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

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
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).
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.
The search space is repeatedly cut in half via binary search, which results in O(log n), the logarithmic number of comparisons.
Yes, it is a divide-and-conquer technique as a binary search breaks the problem down into smaller subproblems.
In sorted arrays, binary search is indeed more efficient than linear search, with an O(log n) time complexity as compared to O(n).
brochureimg

The DevOps Playbook

Simplify deployment with Docker containers.

Streamline development with modern practices.

Enhance efficiency with automated workflows.

left dot patternright dot pattern

Programs tailored for your success

Popular

Management

Data Science

Finance

Technology

Future Tech

Upskill with expert articles

View all
Hero Vired logo
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.

Data Science

Accelerator Program in Business Analytics & Data Science

Integrated Program in Data Science, AI and ML

Accelerator Program in AI and Machine Learning

Advanced Certification Program in Data Science & Analytics

Technology

Certificate Program in Full Stack Development with Specialization for Web and Mobile

Certificate Program in DevOps and Cloud Engineering

Certificate Program in Application Development

Certificate Program in Cybersecurity Essentials & Risk Assessment

Finance

Integrated Program in Finance and Financial Technologies

Certificate Program in Financial Analysis, Valuation and Risk Management

Management

Certificate Program in Strategic Management and Business Essentials

Executive Program in Product Management

Certificate Program in Product Management

Certificate Program in Technology-enabled Sales

Future Tech

Certificate Program in Gaming & Esports

Certificate Program in Extended Reality (VR+AR)

Professional Diploma in UX Design

Blogs
Reviews
Events
In the News
About Us
Contact us
Learning Hub
18003093939     ·     hello@herovired.com     ·    Whatsapp
Privacy policy and Terms of use

© 2024 Hero Vired. All rights reserved