5 ms·
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-it-nearly.ht
by devnonymous 7y ago
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-it-nearly.html?m=1 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.
- smitty1e 7y agoWorking in IT affords occasion to be humble at least daily.
- person_of_color 7y agoWhy does this implementation used signed integers for indices at all?
- MauranKilom 7y agoJava. 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.
- smellia 7y agoIts 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.
- mypalmike 7y agoThis is why integer sign should be part of the operation rather than the type. Every language but assembly gets this wrong.
- agentultra 7y agoA 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.