4 ms·
Ha, you're right! So the algorithm is correct, but I think sort of by accident. If you change the initial check from "if lo > hi then" to "if lo >= hi then",
by dilap 6y ago
Ha, you're right!
So the algorithm is correct, but I think sort of by accident.
If you change the initial check from "if lo > hi then" to "if lo >= hi then", the algorithm remains correct, and does not depend on accessing an out-of-bounds array index.
(The input range to the recursive search is half-open, so the check for an empty range should be greater-than-or-equals, not strict-greater-than.)
- 1-more 6y agoYeah I immediately checked that after commenting since it's exactly the off-by-half thing I never get right without checking and yup, you can end up with a never used code path. What a rollercoaster. Ah well. For this particular thing you do in fact end up with one. In other cases whenever I end up with an unfollowed code path I can usually refactor it out. Non-empty lists are a good way of doing that, for instance.