5 ms·
> A former colleague of mine challenged his grad students to implement an error-free version of binary search. He gave them the specification and verified each
by sigstoat 4y ago
> A former colleague of mine challenged his grad students to implement an error-free version of binary search. He gave them the specification and verified each one: the majority of the submissions had errors.
I was in a class on Isabelle where we had to write and prove correct a binary search function. As I recall, everyone admitted that their first function didn’t work.
- renewiltord 4y agoJava's was broken till '06
- OnionBlender 4y agohttps://en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues https://en.wikipedia.org/wiki/Binary_search_algorithm#Implem... People often do (L+R)/2 but that can overflow. Using L+(R-L)/2 avoids the overflow problem.
- nomel 4y agoAs someone who has a binary search in their interview question, I will claim that far more people run into the problem of trying to do midpoint/2 and midpoint*2, long before overflows.