Parallel Binary Search

Run the binary searches of $q$ queries simultaneously, so that the expensive “apply the first $k$ operations” step is done once per round instead of once per query.

The problem it solves

“There are $m$ operations applied in order. For each of $q$ queries, find the earliest moment at which its condition becomes true.”

Binary searching each query independently costs $O(q\log m)$ rebuilds of the structure — far too slow when a rebuild is $O(m)$ or worse.

The technique

Each query keeps its own interval $[l{o}_i,h{i}_i]$. In each round:

1. Group the queries by their midpoint $mi{d}_i$.
2. Sweep the operations from 1 to $m$ once, and whenever the operation index equals some group’s midpoint, evaluate all queries in that group against the current structure.
3. Narrow each query’s interval based on its result.

After $O(\log m)$ rounds every interval collapses.

vector<int> lo(q, 0), hi(q, m);
while (true) {
    vector<vector<int>> byMid(m + 1);
    bool anyLeft = false;
    for (int i = 0; i < q; i++)
        if (lo[i] < hi[i]) { byMid[(lo[i] + hi[i]) / 2].push_back(i); anyLeft = true; }
    if (!anyLeft) break;
 
    reset();                                        // fresh structure
    for (int t = 1; t <= m; t++) {
        apply(t);                                   // the t-th operation
        for (int i : byMid[t]) {
            if (check(i)) hi[i] = t; else lo[i] = t + 1;
        }
    }
}

Complexity: $O(\log m)$ rounds, each $O(m\cdot \text{apply}+q\cdot \text{check})$.

Worked example: “when does this pair become connected?”

Edges are added one at a time; for each query pair $(u,v)$, find the first edge index after which they are connected.

• apply(t) — dsu.unite(edges[t]), $O(\alpha )$;
• check(i) — dsu.same(u_i, v_i), $O(\alpha )$;
• reset() — a fresh DSU, $O(n)$.

Total $O((n+m+q)\log m\alpha )$. Independently binary searching would be $O(qm\alpha )$.

This is the standard solution to “minimum bottleneck edge on a path” for many queries (also solvable with MST + binary lifting, but parallel binary search generalises further).

More examples

Problem	apply	check
First moment $u$ and $v$ are connected	union an edge	DSU same
First moment a region receives $\ge k$ items	range add on a BIT	prefix query
$k$-th smallest with insertions	insert into a BIT	count $\le$ mid
First moment a subgraph becomes bipartite	union with parity	consistency check
Minimum capacity for all flows to succeed	add an edge	max-flow value
First round in which a player is eliminated	apply a round	evaluate a condition

Parallel binary search vs the alternatives

Technique	Handles	Cost
Parallel binary search	”when does the answer flip” for many queries	$O(\log m)$ rebuilds
Segment tree on time	queries at arbitrary times with add and remove	$O(\log m)$ per operation
CDQ	multi-dimensional dominance	$O(n{\log }^{2}n)$
Persistent structures	online historical queries	$O(\log n)$ per query
Independent binary searches	few queries	$O(q\log m\cdot \text{rebuild})$

The distinguishing feature: parallel binary search needs only an incrementally buildable structure (add-only), not a rollback-able or persistent one — which makes plain DSU sufficient where offline dynamic connectivity would need rollback.

Requirements

1. Each query’s predicate must be monotone in time: once true, always true.
2. The structure must support applying operations in order from a fresh state.
3. All queries must be known up front (this is an offline technique).

If the predicate is not monotone, the technique does not apply — verify this before writing it.

Implementation notes

• Reset the structure completely each round, or use rollbacks; leftover state is the usual bug.
• Bucketing queries by midpoint is what makes one sweep serve all of them — do not sort queries by their own $lo$/$hi$.
• Handle “never becomes true” by initialising $hi=m+1$ and checking for that sentinel at the end.
• The rounds are independent, so this parallelises trivially across threads if that is ever useful.

See also: Binary Search · Offline Query Processing · Dynamic Connectivity