On Parallel Binary Search #1384
Conversation
|
Hello @Kostero and welcome! Thanks for joining the project and thanks for the contribution! Here's some quick initial feedback: Consider putting text in online grammar/spell checker. I noticed than 'Specifically' was misspelled. Also, I'd personally prefer more descriptive variable names rather than Also, consider compiling the given code. What is Also, I think we use snake case for functions and it may make sense to have |
|
Thanks for the feedback. I have fixed some issues. Comments for the remaining ones below.
A and X are mostly there to keep things simple and to not repeat long variables names (especially in the table explaining what we actually do). I would prefer to keep it that way.
I have a problem of changing the variables over and over, after doing all the checks (including compilation). It should work now. I will try to add tests in the follow-up, just wanted to get the first review asap.
I kinda disagree here, as they directly refer to |
src/num_methods/binary_search.md
Outdated
| | **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 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. |
There was a problem hiding this comment.
I'd really prefer to add a bit more of the following:
- Motivation to ever consider doing it in the first place;
- 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
|
Any update here? |
|
Is this dead? |
No description provided.