• Re: 2019 wish list

    From Brian Wood@woodbrian77@gmail.com to comp.lang.c++ on Sat Feb 27 11:41:03 2021
    From Newsgroup: comp.lang.c++

    On Saturday, February 20, 2021 at 9:58:56 AM UTC-6, Tim Rentsch wrote:
    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.

    That's great. Now I wish that my wish list items would
    not be forgotten for a year or two.


    Brian
    --- Synchronet 3.18c-Linux NewsLink 1.113