algorithm
binary search
computational complexity
time complexity
data structures

how to calculate binary search complexity

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

Binary search is a fundamental algorithm in computer science, widely used to find a target value within a sorted array. Understanding the complexity of binary search is crucial for analyzing its efficiency, especially when dealing with large datasets. This article delves into the calculation of binary search complexity, providing technical explanations and examples to clarify the concept.

Understanding Binary Search Algorithm

Binary search works on the divide-and-conquer principle. It repeatedly divides a sorted array into halves until it finds the target value or confirms the value does not exist in the array.

  1. Initialize Two Pointers: Start (start) and end (end) points are initialized at the beginning and the end of the array, respectively.
  2. Calculate Middle Index: The middle index (mid) is calculated using the formula mid = start + (end - start) / 2.
  3. Compare Midpoint with Target:
    • If the middle element is the target, the search is successful.
    • If the middle element is greater, focus on the left half by setting end to mid - 1.
    • If the middle element is smaller, focus on the right half by setting start to mid + 1.
  4. Repeat: Repeat steps 2 and 3 until the target is found or the pointers overlap.

Technical Example

Let's say we have a sorted array: [1, 3, 5, 7, 9, 11, 13, 15] and we want to find the position of 9.

  1. Start with start at 0 and end at 7.
  2. Calculate mid: mid = 0 + (7 - 0) / 2 = 3. Compare element at index 3 (value 7) with 9. Since 9 > 7, adjust start to mid + 1 = 4.
  3. Recalculate mid with new boundaries (4, 7): mid = 4 + (7 - 4) / 2 = 5. Compare element at index 5 (value 11) with 9. Since 9 < 11, adjust end to mid - 1 = 4.
  4. Now, start and end both point to index 4:
    • Compare element at index 4 (value 9) with 9. Target found at index 4.

Time Complexity

The time complexity of binary search is derived from the way it divides the array; it halves the array with each iteration:

  • A single division reduces the problem size by half, which equates to n/2^k = 1 when finally reduced to a single element.
  • Solving for k gives the number of iterations: k = log₂ n. Therefore, the time complexity of binary search is O(log n), where n is the number of elements in the array.

Space Complexity

Binary search has a space complexity of O(1) for the iterative version as it requires only constant space for variables. The recursive version, however, entails a space complexity of O(log n) due to the call stack.

Additional Considerations

Impact of Array Size

Due to its logarithmic time complexity, binary search is highly efficient for large datasets. Its performance improves significantly over linear search, especially as the size of the dataset increases.

Precondition of Sorted Array

A critical precondition for applying binary search is that the array must be sorted. An unsorted array requires sorting beforehand, which affects overall operation time.

Edge Cases

  • Empty array: The algorithm immediately determines that the target is absent.
  • Single element array: A single-step decision if the element matches the target.
  • Repeated elements: Binary search can be adapted to find the first or last occurrence of a target in arrays with duplicates.

Summary Table

Below we summarize the key points related to binary search:

AspectDetails
Algorithm TypeDivide-and-Conquer
Time ComplexityO(log n)
Space ComplexityO(1) (iterative) O(log n) (recursive due to call stack)
PreconditionArray must be sorted
EfficiencyEfficient for large datasets
ApplicationsSearch operations in databases, libraries, etc.

Binary search is a cornerstone algorithm used in numerous computer science applications, valued for its efficiency and a clear understanding of its complexity allows developers to harness its full potential.


Related reading
Course
Intermediate
27 lessons
15 hours
DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course
Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

All Rights Reserved.