Hacker News Reader

Comment by devnonymous | Hacker News Reader

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.

View on HN

Working in IT affords occasion to be humble at least daily.

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.

Why does this implementation used signed integers for indices at all?

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.

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.

This is why integer sign should be part of the operation rather than the type. Every language but assembly gets this wrong.

Reply on news.ycombinator.com