Binary search too hard
- Dominant language
- Julia
- Stars
- 73
- Forks
- 82
- Avg merge
- 2h 17m
- Merged PRs (30d)
- 5
Description
We instruct students to return a range (like `searchsorted` does), but also we guarantee that there is only zero or one instance of the target value in the array unless the student enables the bonus tests. This is confusing.
IMHO, we should have the student provide their own implementations of `searchsortedfirst` (returns the index of the first value >= to the target, which is also the insertion index if you want to insert the target value in the array).
We can test the current behaviour (`searchsorted`-alike) in bonus tests or another exercise.
Students often come up with complicated solutions because they're doing too much work in the loop. We may want to provide a hint about that and/or link to a resource. Here's something I've posted a few times now to students:
> Anyway, the key simplifying observation here is to simplify the body of your while loop so that you never return from it. Instead, arrange things so that you can always return `low:high` after the while loop and have it be correct.
>
> You can read [this article](http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary) for details on how to do that.
Contributor guide
Assessment
This issue has not been assessed yet.