Logarithmic (O(log n))

At a glance: Each step removes a fixed fraction of the remaining possibilities, so the number of steps grows logarithmically.

Jump to: Time complexity · Space complexity · Try it yourself

Understand the growth

Think of finding a word in a sorted dictionary by opening near the middle, then choosing the relevant half. A poor first guess is not fatal because each decision discards roughly half the remaining candidates. Binary search formalizes exactly this idea for random-access sorted data.

After k halvings, at most about n / 2^k candidates remain. Solving n / 2^k <= 1 gives k >= log₂(n). Changing the logarithm base only multiplies the expression by a constant factor, so it does not change the Big O class.

Why halving leads to a logarithm

Binary search works by maintaining a range that could still contain the target. One comparison with the middle element tells us which half can be discarded. After k decisions, the remaining range is roughly n / 2^k; when this becomes at most one element, k is about log₂(n). Doubling the initial range adds approximately one decision rather than doubling the search effort.

A fixed shrink factor other than two leads to the same complexity class. Reducing the candidates to one third per step produces log₃(n) levels, and changing logarithm bases changes only a constant multiplier. What makes the method logarithmic is reliable multiplicative progress, not the mere presence of division in the source code.

The underlying data must allow efficient access to the chosen midpoint. Searching a sorted array satisfies this assumption. If reaching the middle of a linked list takes linear traversal each time, the full process can lose the O(log n) time guarantee. If the collection is unsorted, discarding a half based on its middle value is simply incorrect.

Worked example

For 1,024 candidates, ten exact halvings reduce the interval to one candidate. For 2,048 candidates, eleven halvings suffice. The input doubled, but only one extra halving was added. Actual comparison counts may include a final check or stopping condition depending on the implementation.

Follow a search interval

Search for 23 in [3, 7, 12, 18, 23, 29, 34, 41]. The first midpoint is index 3, value 18, so discard indices 0 through 3. The remaining candidates are [23, 29, 34, 41]; the next midpoint under the code’s inclusive bounds is index 5, value 29, so discard that value and everything to its right. The final interval begins at index 4, where 23 is found on the third comparison.

Searching for a missing value such as 20 uses the same shrinking invariant and finishes with lo > hi; the implementation returns -1. In contrast, a lower-bound search returns the first valid insertion position. Both are logarithmic, but they have different contracts, particularly when duplicate values occur.

Time complexity

Representative time example: Binary search on sorted data.

The usual iterative binary-search routine tests the middle element and keeps only one side. In the worst case it continues until there is no interval left, giving O(log n) comparisons. A successful match at the first middle element is O(1) in the best case. It is essential to specify that the input is sorted and supports efficient random access; repeatedly walking to a middle node in a linked list changes the cost model. The example in the old website used a lower-bound insertion-position variant, not the same return contract as a search that yields -1 when absent.

Prove the interval shrinks

The binary-search loop maintains two invariants: all potential matches lie in [lo, hi], and the interval boundaries move strictly inward after every unsuccessful comparison. mid = lo + (hi - lo) / 2 avoids an overflow-prone addition of the two endpoints in common integer implementations. Either lo = mid + 1 or hi = mid - 1 removes the midpoint, so the loop cannot get stuck.

Best-case time is Θ(1) if the very first midpoint matches. Worst-case time is Θ(log n) because each comparison leaves at most about half the candidates. A claim about average time needs a distribution of search targets. The O(log n) comparison count assumes midpoint reads and comparisons cost O(1), which is appropriate for a fixed-width element in a random-access array.

C#

C# | Logarithmic.cs

static int BinarySearch(int[] values, int target)
{
    int lo = 0, hi = values.Length - 1;
    while (lo <= hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (values[mid] == target) return mid;
        if (values[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

C++

C++ | logarithmic.cpp

#include <vector>

int binarySearch(const std::vector<int>& values, int target) {
    int lo = 0, hi = static_cast<int>(values.size()) - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (values[mid] == target) return mid;
        if (values[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Analysis: Iterative binary search requires a sorted array; its worst-case time is O(log n).

The C++ version illustrates the same operation. The container, compiler and any functions called by the example still matter when analyzing a complete program.

Space complexity

Representative memory example: Recursive halving depth.

A recursive halving routine can create one live call frame for every remaining level. Only one recursive branch is active at a time, yet each paused caller still occupies memory until the deepest call returns. The depth is Θ(log n), so stack usage is O(log n). Iterative binary search instead keeps a fixed set of indices and has O(1) auxiliary space. Neither conclusion tells you how much memory the original input array occupies.

Distinguish iteration, recursion and branching

The iterative binary search keeps lo, hi, mid and the target in a constant number of variables: Θ(1) auxiliary space. The array may be large, but it was supplied by the caller. The recursive Visit(n / 2) memory example instead creates one live frame for each halving until n <= 1. At n = 1,024, there are about eleven simultaneously active calls including the base case, which yields Θ(log n) stack depth.

Only one recursive child is active at a time in that example. A divide-and-conquer routine with two recursive children can still have O(log n) stack depth if it executes one child before the other; however, it may do much more total work. If every frame retains a growing buffer, stack memory is not simply proportional to the number of frames. For large inputs, an iterative implementation also avoids stack-overflow concerns.

C#

C# | Logarithmic.cs

void Visit(int n)
{
    if (n <= 1) return;
    Visit(n / 2);
}

C++

C++ | logarithmic.cpp

void visit(int n) {
    if (n <= 1) return;
    visit(n / 2); // one live call per halving
}

Analysis: This recursive example has O(log n) call-stack depth; iterative binary search uses O(1) auxiliary space.

The stated bound describes stored elements and active call frames. Actual byte counts also depend on runtime, allocator and element representation.

When logarithmic search is a good fit

Use binary search when the candidates are ordered and a midpoint query reliably tells you which side to keep. It is useful for finding an exact target, the first value at least x (lower bound), or a threshold where a monotone predicate changes from false to true. Balanced search trees likewise aim for logarithmic search height, but their guarantees depend on their balancing rules.

Logarithmic time does not automatically mean logarithmic memory. It also does not mean that every recursive function is logarithmic: a recursion that decrements n by one has Θ(n) depth, and a recursion that scans all n items at every halving level can cost Θ(n log n) time. State the progress measure and the work per level before classifying an algorithm.

Practical example: threshold search

Imagine sorted player scores and a leaderboard that must find the first score at least 1,000. A lower-bound binary search is a natural choice: after comparing the midpoint score with 1,000, discard the half that cannot contain the first qualifying score. The algorithm remains O(log n), even if many players have identical scores, provided the boundary rules consistently select the leftmost qualifying position.

By contrast, asking for all qualifying players can require reporting thousands of results. Finding the starting index may take O(log n), but enumerating k matching players adds O(k) output work. The full operation is therefore O(log n + k). This distinction becomes important when a fast lookup is followed by an expensive UI or export operation.

Common mistake

Watch out: A halving recursion does not automatically have O(log n) time: if it processes all n values at each level, its work can be O(n log n). Always count the operations inside every recursive call.

Try it yourself

Predict the number of halvings for 64, 1,024 and 65,536 candidates. Then compare iterative binary-search space with recursive halving stack depth.

1. Define exactly what n represents.
2. Count the key operation in the best and worst case where relevant.
3. Count the maximum simultaneously live memory.
4. Check your prediction in the Big O explorer.

Continue learning

Big O overview · Time complexity · Space complexity · Compare classes