Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

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.

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

Already on GitHub?Sign in to your account

Open
Kostero wants to merge10 commits intomain
base:main
Choose a base branch
Loading
frompbs
Open
Changes fromall commits
Commits
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 deletionssrc/num_methods/binary_search.md
View file
Open in desktop
Original file line numberDiff line numberDiff 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. howthis 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 onhow 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.

Usingstd::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 overstd::map.

Also in this formulation it should be sufficient to e.g. have an array ofM 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
[8]ページ先頭
©2009-2025 Movatter.jp