Skip to content

On Parallel Binary Search #1384

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
wants to merge 10 commits into
base: main
Choose a base branch
from
Open

On Parallel Binary Search #1384

Changes from all commits
Commits
Show all changes
10 commits
Select commit Hold shift + click to select a range
ba84614
On Parallel Binary Search
Kostero Oct 27, 2024
d2a3810
Small fixes.
Kostero Oct 27, 2024
2f5e0bf
Remove latex in comments.
Kostero Oct 27, 2024
9cb53f3
Fix naming in comments.
Kostero Oct 27, 2024
5b4e4df
Unify sides in conditions.
Kostero Oct 27, 2024
c1cccdd
Typo.
Kostero Oct 27, 2024
994c1f2
Tenses.
Kostero Oct 27, 2024
56e7840
Some fixes.
Kostero Oct 27, 2024
8629e6e
Fixes 2.
Kostero Oct 27, 2024
5d87760
N-1 to N.
Kostero Oct 27, 2024
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
62 changes: 62 additions & 0 deletions src/num_methods/binary_search.md
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -138,6 +138,63 @@ Another noteworthy way to do binary search is, instead of maintaining an active

This paradigm is widely used in tasks around trees, such as finding lowest common ancestor of two vertices or finding an ancestor of a specific vertex that has a certain height. It could also be adapted to e.g. find the $k$-th non-zero element in a Fenwick tree.

## Parallel Binary Search

<small>Note that this section follows the description in [Sports programming in practice](https://kostka.dev/sp/).</small>
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Is the intention here to provide a reference for further reading, or an attribution? I think it is more common to integrate references in the text (see e.g. how this is linked above in the article) or put them in some kind of further reading section at the end.

Also, to make sure, you understand that by putting the text from the book here you also make it licensed under CC BY-SA 4.0?


Imagine that we want to answer $Z$ queries about the index of the largest value less than or equal to some $X_i$ (for $i=1,2,\ldots,Z$) in a sorted 0-indexed array $A$. Naturally, each query can be answered using binary search.
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It is $Z$ here, but $M$ in the code. Best to make it consistent, and maybe using $Z$ in both makes sense, given mhayter's comment that $m$ is already used for midpoint.


Specifically, let us consider the following array $A = [1,3,5,7,9,9,13,15]$
with queries: $X = [8,11,4,5]$. We can use binary search for each query sequentially.

| query | \( X_1 = 8 \) | \( X_2 = 11 \) | \( X_3 = 4 \) | \( X_4 = 5 \) |
|--------|------------------------|------------------------|-----------------------|-----------------------|
| **step 1** | answer in \([0,8)\) | answer in \([0,8)\) | answer in \([0,8)\) | answer in \([0,8)\) |
| | check \( A_4 \) | check \( A_4 \) | check \( A_4 \) | check \( A_4 \) |
| | \( X_1 < A_4 = 9 \) | \( X_2 \geq A_4 = 9 \) | \( X_3 < A_4 = 9 \) | \( X_4 < A_4 = 9 \) |
| **step 2** | answer in \([0,4)\) | answer in \([4,8)\) | answer in \([0,4)\) | answer in \([0,4)\) |
| | check \( A_2 \) | check \( A_6 \) | check \( A_2 \) | check \( A_2 \) |
| | \( X_1 \geq A_2 = 5 \) | \( X_2 < A_6 = 13 \) | \( X_3 < A_2 = 5 \) | \( X_4 \geq A_2 = 5 \) |
| **step 3** | answer in \([2,4)\) | answer in \([4,6)\) | answer in \([0,2)\) | answer in \([2,4)\) |
| | check \( A_3 \) | check \( A_5 \) | check \( A_1 \) | check \( A_3 \) |
| | \( X_1 \geq A_3 = 7 \) | \( X_2 \geq A_5 = 9 \) | \( X_3 \geq A_1 = 3 \) | \( X_4 < A_3 = 7 \) |
| **step 4** | answer in \([3,4)\) | answer in \([5,6)\) | answer in \([1,2)\) | answer in \([2,3)\) |
| | \( index = 3 \) | \( index = 5 \) | \( index = 1 \) | \( index = 2 \) |
Comment on lines +150 to +162
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
| query | \( X_1 = 8 \) | \( X_2 = 11 \) | \( X_3 = 4 \) | \( X_4 = 5 \) |
|--------|------------------------|------------------------|-----------------------|-----------------------|
| **step 1** | answer in \([0,8)\) | answer in \([0,8)\) | answer in \([0,8)\) | answer in \([0,8)\) |
| | check \( A_4 \) | check \( A_4 \) | check \( A_4 \) | check \( A_4 \) |
| | \( X_1 < A_4 = 9 \) | \( X_2 \geq A_4 = 9 \) | \( X_3 < A_4 = 9 \) | \( X_4 < A_4 = 9 \) |
| **step 2** | answer in \([0,4)\) | answer in \([4,8)\) | answer in \([0,4)\) | answer in \([0,4)\) |
| | check \( A_2 \) | check \( A_6 \) | check \( A_2 \) | check \( A_2 \) |
| | \( X_1 \geq A_2 = 5 \) | \( X_2 < A_6 = 13 \) | \( X_3 < A_2 = 5 \) | \( X_4 \geq A_2 = 5 \) |
| **step 3** | answer in \([2,4)\) | answer in \([4,6)\) | answer in \([0,2)\) | answer in \([2,4)\) |
| | check \( A_3 \) | check \( A_5 \) | check \( A_1 \) | check \( A_3 \) |
| | \( X_1 \geq A_3 = 7 \) | \( X_2 \geq A_5 = 9 \) | \( X_3 \geq A_1 = 3 \) | \( X_4 < A_3 = 7 \) |
| **step 4** | answer in \([3,4)\) | answer in \([5,6)\) | answer in \([1,2)\) | answer in \([2,3)\) |
| | \( index = 3 \) | \( index = 5 \) | \( index = 1 \) | \( index = 2 \) |
| Query | \( X_1 = 8 \) | \( X_2 = 11 \) | \( X_3 = 4 \) | \( X_4 = 5 \) |
|--------|:----------------------------------------:|:-----------------------------------------:|:------------------------------------------:|:------------------------------------------:|
| **Step 1** | Answer in \([0,8)\) <br> Check \( A_4 \) <br> \( X_1 < A_4 = 9 \) | Answer in \([0,8)\) <br> Check \( A_4 \) <br> \( X_2 \geq A_4 = 9 \) | Answer in \([0,8)\) <br> Check \( A_4 \) <br> \( X_3 < A_4 = 9 \) | Answer in \([0,8)\) <br> Check \( A_4 \) <br> \( X_4 < A_4 = 9 \) |
| **Step 2** | Answer in \([0,4)\) <br> Check \( A_2 \) <br> \( X_1 \geq A_2 = 5 \) | Answer in \([4,8)\) <br> Check \( A_6 \) <br> \( X_2 < A_6 = 13 \) | Answer in \([0,4)\) <br> Check \( A_2 \) <br> \( X_3 < A_2 = 5 \) | Answer in \([0,4)\) <br> Check \( A_2 \) <br> \( X_4 \geq A_2 = 5 \) |
| **Step 3** | Answer in \([2,4)\) <br> Check \( A_3 \) <br> \( X_1 \geq A_3 = 7 \) | Answer in \([4,6)\) <br> Check \( A_5 \) <br> \( X_2 \geq A_5 = 9 \) | Answer in \([0,2)\) <br> Check \( A_1 \) <br> \( X_3 \geq A_1 = 3 \) | Answer in \([2,4)\) <br> Check \( A_3 \) <br> \( X_4 < A_3 = 7 \) |
| **Step 4** | Answer in \([3,4)\) <br> \( index = 3 \) | Answer in \([5,6)\) <br> \( index = 5 \) | Answer in \([1,2)\) <br> \( index = 1 \) | Answer in \([2,3)\) <br> \( index = 2 \) |

Let's join rows for each step and align by center in columns.


We generally process this table by columns (queries), but notice that in each row we often repeat access to certain values of the array. To limit access to these values, we can process the table by rows (steps). This does not make huge difference in our small example problem (as we can access all elements in $\mathcal{O}(1)$), but in more complex problems, where computing these values is more complicated, this might be essential to solve these problems efficiently. Moreover, note that we can arbitrarily choose the order in which we answer questions in a single row. Let us look at the code implementing this approach.
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'd really prefer to add a bit more of the following:

  1. Motivation to ever consider doing it in the first place;
  2. Some specific examples on how using this reduces the complexity.

I think for the latter there are some very simple applications like finding order of key on segment in $O(\log n)$?

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
We generally process this table by columns (queries), but notice that in each row we often repeat access to certain values of the array. To limit access to these values, we can process the table by rows (steps). This does not make huge difference in our small example problem (as we can access all elements in $\mathcal{O}(1)$), but in more complex problems, where computing these values is more complicated, this might be essential to solve these problems efficiently. Moreover, note that we can arbitrarily choose the order in which we answer questions in a single row. Let us look at the code implementing this approach.
We generally process this table by columns (queries), but notice that in each row we often repeat access to certain values of the array. To limit access to these values, we can process the table by rows (steps). This does not make huge difference in our small example problem (as we can access all elements in $O(1)$), but in more complex problems, where computing these values is more complicated, this might be essential to solve these problems efficiently. Moreover, note that we can arbitrarily choose the order in which we answer questions in a single row. Let us look at the code implementing this approach.

Other parts of the article don't use mathcal with O.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Moreover, note that we can arbitrarily choose the order in which we answer questions in a single row.

Don't we actually really care about doing it in increasing order of $m$ in certain scanline-like applications?


```{.cpp file=parallel-binary-search}
// Computes the index of the largest value in a sorted array A less than or equal to X_i for all i.
vector<int> parallel_binary_search(vector<int>& A, vector<int>& X) {
int N = A.size();
int M = X.size();
vector<int> l(M, -1), r(M, N);

for (int step = 1; step <= ceil(log2(N)); ++step) {
// Map to store indices of queries asking for this value.
unordered_map<int, vector<int>> m_to_queries;
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Using std::unordered_map is generally considered an anti-pattern in modern CP, given that it's constantly getting hacked by certain enthusiasts in CF rounds, unless proper randomization is used, and even when it is used properly, it rarely provides significant practical benefits over std::map.

Also in this formulation it should be sufficient to e.g. have an array of M vectors?


// Calculate middle point and populate the m_to_queries map.
for (int i = 0; i < M; ++i) {
int m = (l[i] + r[i]) / 2;
m_to_queries[m].push_back(i);
}

// Process each value in m_to_queries.
for (const auto& [m, queries]: m_to_queries) {
for (int query : queries) {
if (X[query] < A[m]) {
r[query] = m;
} else {
l[query] = m;
}
}
}
}
return l;
}
```

## Practice Problems

* [LeetCode - Find First and Last Position of Element in Sorted Array](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/)
Expand All @@ -154,3 +211,8 @@ This paradigm is widely used in tasks around trees, such as finding lowest commo
* [Codeforces - GukiZ hates Boxes](https://codeforces.com/problemset/problem/551/C)
* [Codeforces - Enduring Exodus](https://codeforces.com/problemset/problem/645/C)
* [Codeforces - Chip 'n Dale Rescue Rangers](https://codeforces.com/problemset/problem/590/B)

### Parallel Binary Search

* [Szkopul - Meteors](https://szkopul.edu.pl/problemset/problem/7JrCYZ7LhEK4nBR5zbAXpcmM/site/?key=statement)
* [AtCoder - Stamp Rally](https://atcoder.jp/contests/agc002/tasks/agc002_d)
Loading