Skip to content

Commit 8629e6e

Browse files
committed
Fixes 2.
1 parent 56e7840 commit 8629e6e

File tree

1 file changed

+11
-12
lines changed

1 file changed

+11
-12
lines changed

src/num_methods/binary_search.md

Lines changed: 11 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -168,31 +168,30 @@ We generally process this table by columns (queries), but notice that in each ro
168168
vector<int> parallel_binary_search(vector<int>& A, vector<int>& X) {
169169
int N = A.size();
170170
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);
173172

174173
for (int step = 1; step <= ceil(log2(N)); ++step) {
175174
// 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;
177176

178-
// Calculate mid and populate the mid_to_queries map.
177+
// Calculate middle point and populate the m_to_queries map.
179178
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);
182181
}
183182

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) {
186185
for (int query : queries) {
187-
if (X[query] < A[mid]) {
188-
right[query] = mid;
186+
if (X[query] < A[m]) {
187+
r[query] = m;
189188
} else {
190-
left[query] = mid;
189+
l[query] = m;
191190
}
192191
}
193192
}
194193
}
195-
return left;
194+
return l;
196195
}
197196
```
198197

0 commit comments

Comments
 (0)