Timeline for Fastest search algorithm in a sorted list with certain error rate-limiting constraints
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 3, 2017 at 22:38 | comment | added | LiveOverflow | Instead of doing a binary search guess in the middle of the current search window, I do a split in a 15:85 ratio. That's what I meant with 0.15 ratio | |
| Jul 3, 2017 at 13:44 | comment | added | rus9384 | By 0.15 you mean 85% of maximum value? Otherwise I don't understand it, since it tells that error is given if you answer was too low. | |
| Jul 3, 2017 at 13:00 | answer | added | orlp | timeline score: 2 | |
| Jul 2, 2017 at 23:24 | history | tweeted | twitter.com/StackCompSci/status/881654832226062336 | ||
| Jul 2, 2017 at 18:03 | comment | added | LiveOverflow | I know already that the egg algorithm is pretty constant in time with 1920s, and that the best ratio for the skewed binary search is at ~0.22 with an average of ~2000s (see graphic). I added a few sentences I hope this is now clearer in the main question. But I think my three questions are already very clear. | |
| Jul 2, 2017 at 18:00 | history | edited | LiveOverflow | CC BY-SA 3.0 |
clarifications
|
| Jul 2, 2017 at 17:32 | comment | added | D.W.♦ | Please edit the question to clarify your question -- don't just leave clarifications in the comments. We want questions to stand on their own, so people don't have to read the comments to understand what you are asking. Perhaps more useful questions to ask would be: what is the expected running time of the skewed binary search algorithm? You can then compare that to the running time of the egg drop algorithm (which you already know). I'm not sure it will be possible to provide a better explanation than that. | |
| Jul 2, 2017 at 16:03 | comment | added | LiveOverflow | Intuitively I would have thought the modified binary search solves this problem as efficiently as possible with the given time constraints. Though it turns out the algorithm from the egg problem performs better. I don't understand why. So I came up with three questions. First, why is the sweet spot for the skew at ~0.22? Second, why is the egg algorithm better, I imagined the egg problem to approach binary search the more eggs you have. And third, is the egg algorithm already the fastest one, or is there a "better" one. I guess with "better" I mean average time required to find the number. | |
| Jul 2, 2017 at 15:43 | comment | added | Yuval Filmus | I'm not sure what kind of answer you are looking for. Two algorithms perform differently because they are different algorithms. | |
| Jul 2, 2017 at 12:01 | comment | added | LiveOverflow | Oh I see yeah. I did state that I want the fastest, but was not clear on best/worst cases or consistency etc. To be honest with you, I don't know. I guess the constraint is to always make it in time. But my personal main question is, why is the algorithm for the egg problem is so much faster and more consistent than the skewed binary search. | |
| Jul 2, 2017 at 9:30 | comment | added | Yuval Filmus | One thing is missing in your description. What is your objective? Are you trying to minimize the expected running time, under the constraint that you always make it? Are you trying to minimize some linear combination of expected running time and failure probability? Are you trying to minimize worst case running time? | |
| Jul 2, 2017 at 0:04 | review | First posts | |||
| Jul 2, 2017 at 8:06 | |||||
| Jul 2, 2017 at 0:03 | history | asked | LiveOverflow | CC BY-SA 3.0 |