News for hackers. Stuff that matters.
Re:On Binary Search by bla3 on Thursday October 31, 2019 @08:26AM (#21407945)
Your loop body looks incorrect. You're both adding 1 when updating low and subtracting 1 when updating high -- but you let the high index start at array.length. It's possible that your additional || clause before the high update mitigates the effects of this, but it's at best inefficient. To implement binary search effectively, it's useful to think about invariants. https://zhu45.org/posts/2018/Jan/12/how-to-write-binary-sear... looks like a decent post on this topic. Searching for "binary search loop invariant" or similar will find many similar articles. I recommend giving them a look, it's a useful thought framework for this algorithm :)
Re:On Binary Search by bla3 on Thursday October 31, 2019 @08:35AM (#21408023)
The highest-rated comment on https://stackoverflow.com/questions/504335/what-are-the-pitf... is also good.
Re:On Binary Search by claes-magnus on Thursday October 31, 2019 @09:16AM (#21408346)
Thank you!