@@ -168,31 +168,30 @@ We generally process this table by columns (queries), but notice that in each ro
168
168
vector<int > parallel_binary_search (vector<int >& A, vector<int >& X) {
169
169
int N = A.size();
170
170
int M = X.size();
171
- vector<int > left(M, -1);
172
- vector<int > right(M, N-1);
171
+ vector<int > l(M, -1), r(M, N-1);
173
172
174
173
for (int step = 1; step <= ceil(log2(N)); ++step) {
175
174
// Map to store indices of queries asking for this value.
176
- unordered_map<int, vector<int>> mid_to_queries ;
175
+ unordered_map<int, vector<int>> m_to_queries ;
177
176
178
- // Calculate mid and populate the mid_to_queries map.
177
+ // Calculate middle point and populate the m_to_queries map.
179
178
for (int i = 0; i < M; ++i) {
180
- int mid = (left [i] + right [i]) / 2;
181
- mid_to_queries[mid ].push_back(i);
179
+ int m = (l [i] + r [i]) / 2;
180
+ m_to_queries[m ].push_back(i);
182
181
}
183
182
184
- // Process each value in mid_to_queries .
185
- for (const auto& [mid , queries]: mid_to_queries ) {
183
+ // Process each value in m_to_queries .
184
+ for (const auto& [m , queries]: m_to_queries ) {
186
185
for (int query : queries) {
187
- if (X[query] < A[mid ]) {
188
- right [query] = mid ;
186
+ if (X[query] < A[m ]) {
187
+ r [query] = m ;
189
188
} else {
190
- left [query] = mid ;
189
+ l [query] = m ;
191
190
}
192
191
}
193
192
}
194
193
}
195
- return left ;
194
+ return l ;
196
195
}
197
196
```
198
197
0 commit comments