Formula & Calculator
Binary Search Time Complexity
Time complexity of binary search in a sorted array.
Interpretation
Binary search time complexity is O(log n) – it halves the search space at each step. It is highly efficient for sorted data. Example: Searching among 1,000,000 elements takes at most log₂(1e6) ≈ 20 comparisons.
Variables
| Symbol | Quantity | Unit |
|---|---|---|
| n | Number of elements | — |
| O(1) | Best-case time complexity | Comparisons |
| O(log n) | Average-case time complexity | Comparisons |
| O(log n) | Worst-case time complexity | Comparisons |
| O(1) | Iterative space complexity | Memory |
What it means
Binary search is a classic algorithm for finding a target value in a sorted array. At each step, it compares the target with the middle element, eliminating half of the remaining elements. This divide‑and‑conquer strategy yields a time complexity of O(log n), meaning the number of comparisons grows logarithmically with the input size. In practice, this makes binary search orders of magnitude faster than linear search for large datasets. The algorithm requires the data to be sorted beforehand, which may add an overhead if sorting is not already done. Binary search is widely used in standard libraries (e.g., in C++ lower_bound, Python bisect) and forms the basis for many other algorithms, including interpolation search and binary search trees. Its space complexity is O(1) for iterative implementation, making it memory‑efficient. Understanding O(log n) complexity is crucial for designing efficient systems that handle large volumes of sorted data.
Worked example
Binary Search Time Complexity – Two Examples
Real‑World| Parameter | Value |
|---|---|
| n (pages) | 1,024 |
| Steps required | log₂(1,024) = 10 |
| Parameter | Value |
|---|---|
| n (records) | 1,048,576 |
| Steps required | log₂(1,048,576) = 20 |
Common mistakes
- Logarithm base: Binary search uses base‑2 logarithms (log₂ n) – not natural log (ln) or log₁₀.
- Input must be sorted: Binary search only works on sorted arrays; applying it to unsorted data gives incorrect results.
- Integer division: When computing the middle index, use (low+high)//2 in integer arithmetic; beware of overflow in some languages.
- Complexity notation: O(log n) is for the average/worst case of binary search; the best case is O(1).
- Recursive overhead: The recursive version uses O(log n) stack space, while iterative uses O(1) – choose appropriately.
Applications
Binary search is a classic divide‑and‑conquer algorithm that finds a target value in a sorted array by repeatedly halving the search interval. Its time complexity of O(log n) makes it exceptionally efficient for large datasets, as the number of steps grows logarithmically with the input size. This efficiency is critical in applications ranging from database indexing and file system lookups to algorithm design and competitive programming. Binary search is also the foundation for many other algorithms, such as binary search trees, interpolation search, and solving equations by numerical methods. In real‑world systems, it powers autocomplete features, dictionary lookups, and even the `bsearch` function in standard libraries. Understanding its complexity enables engineers to choose the right search strategy and to analyse the performance of systems that rely on sorted data, ensuring fast retrieval and low latency.
- Searching in sorted arrays and lists
- Implementation of binary search trees and balanced trees
- Database indexing (B‑trees and other structures)
- Algorithm analysis and complexity theory
- Numerical methods (root finding, binary search on answer)
Frequently Asked Questions
The time complexity of binary search is O(log n) in the worst and average cases. This means the number of comparisons grows logarithmically with the input size. For an array of 1 million elements, binary search requires at most log₂(1,000,000) ≈ 20 comparisons – far faster than linear search.
Binary search requires the input array to be sorted (either ascending or descending). Additionally, it assumes random access to elements (like an array) and that the search space is contiguous. It does not work on linked lists without extra data structures.
- Worst‑case: O(log n) – when the target is not present or is the last element checked.
- Best‑case: O(1) – when the target is exactly the middle element.
- Average‑case: O(log n) – on average, the number of comparisons is close to log₂(n).
- Iterative binary search uses O(1) extra space (only a few variables).
- Recursive binary search uses O(log n) space due to the call stack, which stores the state of each recursive call.
Linear search is O(n) – for n elements, it may check every element. Binary search is O(log n), which is exponentially faster for large n. For n=1,000,000, linear search takes up to 1,000,000 comparisons, while binary search only needs ~20. However, binary search requires a sorted array, which adds sorting overhead.
Yes, but the basic algorithm finds some occurrence of the target. To find the first or last occurrence, you need a modified version that continues searching after a match. The complexity remains O(log n).
- Off‑by‑one errors – incorrectly updating low and high indices (e.g., mid+1, mid‑1).
- Using integer overflow – when computing mid = (low+high)/2, for large arrays (e.g., >2³¹), this can overflow; use low + (high‑low)/2.
- Forgetting to sort the array – binary search on an unsorted array gives incorrect results.
- Not handling empty arrays – always check if the array is empty before searching.
- Searching in sorted databases and dictionaries.
- Debugging – using binary search to find the commit that introduced a bug (bisect).
- Numerical methods – root finding (bisection method).
- Machine learning – hyperparameter tuning (grid search with binary search for thresholds).
If the array is not strictly sorted, binary search will fail. However, if you have a monotonic function (e.g., a predicate that is false then true), you can use binary search on the index space to find the boundary. This is called binary search on the answer and is common in competitive programming.
Interpolation search improves on binary search for uniformly distributed data by estimating the position of the target. Its average complexity is O(log log n), but worst‑case is O(n). Binary search is more predictable and guaranteed O(log n), making it the standard choice for generic sorted arrays.