Skip to content

Commit 3eb4851

Browse files
author
Bartosz Kostka
committed
Fix math mode in one equation.
1 parent 59c381b commit 3eb4851

File tree

1 file changed

+1
-1
lines changed

1 file changed

+1
-1
lines changed

src/num_methods/binary_search.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -142,7 +142,7 @@ This paradigm is widely used in tasks around trees, such as finding lowest commo
142142

143143
When we are faced with multiple queries that can each be solved with a binary search, it is sometimes too slow to solve them one by one. Parallel Binary Search is a technique that allows us to solve all of these queries simultaneously, often leading to a significant performance improvement. The main idea is to perform the binary search for all queries at the same time (in parallel), step by step. This is particularly effective when the check function for the binary search is costly and can be optimized by processing queries in batches.
144144

145-
Consider a scenario where we have $Q$ queries, and for each query $q$, we need to find the smallest value $x$ that satisfies a certain condition $P(q, x)$. If $P(q, x)$ is monotonic on $x$, we can use binary search for each query. This would result in a total complexity of $O(Q \cdot \log(\t{range}) \cdot T_{check})$, where $T_{check}$ is the time to evaluate $P(q, x)$.
145+
Consider a scenario where we have $Q$ queries, and for each query $q$, we need to find the smallest value $x$ that satisfies a certain condition $P(q, x)$. If $P(q, x)$ is monotonic on $x$, we can use binary search for each query. This would result in a total complexity of $O(Q \cdot \log(range) \cdot T_{check})$, where $T_{check}$ is the time to evaluate $P(q, x)$.
146146

147147
Parallel binary search optimizes this by changing the order of operations. Instead of processing each query independently, we process all queries simultaneously, step by step. In each step of the binary search, we compute the middle points $m_i$ for all queries and group the queries by their middle point. This is particularly powerful if the check function $P(q, x)$ has a structure that allows for efficient batching or updates.
148148

0 commit comments

Comments
 (0)