News for hackers. Stuff that matters.
Re:On Binary Search by devnonymous on Wednesday October 30, 2019 @06:39PM (#21403682)
Each time I see an implementation of binary search like this I can't help but recall:

https://ai.googleblog.com/2006/06/extra-extra-read-all-about...

Which reminds me just how young the field of computer science is and how even the ^well known^, fundamental algorithms might have buggy implementations.

Re:On Binary Search by smitty1e on Wednesday October 30, 2019 @06:49PM (#21403794)
Working in IT affords occasion to be humble at least daily.
Re:On Binary Search by agentultra on Wednesday October 30, 2019 @07:08PM (#21403979)
A friend of mine did an experiment with his grad students in his Formal Methods class.

They all submitted their implementation of binary search and he modelled them each in TLA+. The majority of them all had errors.

Re:On Binary Search by person_of_color on Wednesday October 30, 2019 @07:07PM (#21403973)
Why does this implementation used signed integers for indices at all?
Re:On Binary Search by MauranKilom on Wednesday October 30, 2019 @07:21PM (#21404097)
Java. There are no unsigned integers in Java. Many would consider that a benefit (although opinions vary on signed vs unsigned bytes). FWIW, the creators of C++ have stated that they'd go with signed integers for e.g. indexes in the library interfaces nowadays (but it's way too late to change that).

Popular problem with using unsigned : Write a reverse for loop from n (exclusive) to 0 (inclusive). See if you can do it without discarding your two most intuitive (but wrong) approaches.

Re:On Binary Search by smellia on Thursday October 31, 2019 @02:19AM (#21406156)
Its the opposite. Its easy to write such a loop with unsigned ints: for(x=top;x<=top;x--). However you can't reliably write a loop spanning the whole space with signed ints without breaking the no-overflow rules. With unsigned you can do x=0;do{stuff(x);}while(++x); Good luck doing this with signed ints.
Re:On Binary Search by mypalmike on Thursday October 31, 2019 @10:07AM (#21408915)
This is why integer sign should be part of the operation rather than the type. Every language but assembly gets this wrong.