During the execution of the algorithm, we never evaluate neither $A_L$ nor $A_R$, as $L < M < R$. In the end, $L$ will be the index of the last element that is not greater than $k$ (or $-1$ if there is no such element) and $R$ will be the index of the first element larger than $k$ (or $n$ if there is no such element).

**Note.** Calculating`m` as`m = (r + l) / 2` can lead to overflow if`l` and`r` are two positive integers, and this error lived about 9 years in JDK as described in the[blogpost](https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html). Some alternative approaches include e.g. writing`m = l + (r - l) / 2` which always works for positive integer`l` and`r`, but might still overflow if`l` is a negative number. If you use C++20, it offers an alternative solution in the form of`m = midpoint(l, r)` which always works correctly.

**Note.** Calculating`m` as`m = (r + l) / 2` can lead to overflow if`l` and`r` are two positive integers, and this error lived about 9 years in JDK as described in the[blogpost](https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html). Some alternative approaches include e.g. writing`m = l + (r - l) / 2` which always works for positive integer`l` and`r`, but might still overflow if`l` is a negative number. If you use C++20, it offers an alternative solution in the form of`m =std::midpoint(l, r)` which always works correctly.

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.

[^1] Imaginethatwe want to answer $Z$ queries abouttheindex of the largest value less than or equal to some $X_i$ (for $i=1,2,\ldots,Z$) in some sorted 0-indexed array $A$. Naturally, each query can be answered using binary search.

<small>Notethatthis section is followingthedescription in[Sports programming in practice](https://kostka.dev/sp/).</small>

Specifally, let us consider the following array $A$:

| $A_0$| $A_1$| $A_2$| $A_3$| $A_4$| $A_5$| $A_6$| $A_7$|

|-------|-------|-------|-------|-------|-------|-------|-------|

| 1| 3| 5| 7| 9| 9| 13| 15|

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 some sorted 0-indexed array $A$. Naturally, each query can be answered using binary search.

Specifally, 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.

<table>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

</table>

| 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\)|

We generally process this table by columns (queries), but notice that in each row we often repeat access to certain values of our array. To limit access to the 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.

vector<int>ParallelBinarySearch(vector<int>& A, vector<int>& X) {

int N = A.size();

int M = X.size();

vector<int>P(M, -1);

vector<int>Q(M, N-1);

vector<int>left(M, -1);

vector<int>right(M, N-1);