Jorgen Grahn <grahn...@snipabacken.se> writes:
On Sun, 2021-01-03, Tiib wrote:
...
The resulting naive garbage is what I've learned to frown at. Anecdotal >> history of binary search is most clear example of what I observe from
day to day:
"When Jon Bentley assigned binary search as a problem in a
course for professional programmers, he found that ninety
percent failed to provide a correct solution after several hours
of working on it, mainly because the incorrect implementations
failed to run or returned a wrong answer in rare edge cases. A
study published in 1988 shows that accurate code for it is only
found in five out of twenty textbooks."
<https://en.wikipedia.org/wiki/Binary_search_algorithm>
That's weird. I remember the class circa 1991 when we tried to
implement binary search, and I remember who came up with the right solution (not me). We all knew (or learned) it was hard and, more importantly, we knew how to prove an implementation was correct (with invariants and such).
Perhaps our education was better than average, but why bother teaching binary search if you don't do it properly?I had the good fortune to take a course where the material and
textbook was that of Dijkstra's A Discipline of Programming. So
I got used to thinking in terms of invariants and using them to
write programs correctly. I don't remember for sure if it was
part of this course but certainly my recollection associates with
this course learning how to write binary search in a way that is
both simple and verifiably correct.
The discussion suggested to me a programming exercise, two
versions of binary search:
version 1: give the index of the first possible match,
that is, the smallest index value if more
than one element matches
version 2: give the index of the last possible match,
that is, the largest index value if more
than one element matches
I had fun with this exercise (and it didn't go as quickly as I
was expecting). I hope some people here find it fun too.
Sysop: | DaiTengu |
---|---|
Location: | Appleton, WI |
Users: | 593 |
Nodes: | 10 (1 / 9) |
Uptime: | 70:44:15 |
Calls: | 6284 |
Calls today: | 7 |
Files: | 181857 |
Messages: | 1246589 |
Posted today: | 2 |